Site Map | College of Engineering | UC Davis | MyUCDavis

ECS 221 FORMAL LANGUAGE THEORY (3) III

Lecture: 3 hours

Prerequisite: Course ECS 220

Grading: Letter, based on 2 midterms and one final

Catalog Description:
Definition and properties of formal languages, deterministic context-free languages, context-sensitive languages, abstract families of languages, special topics of current interest

Goals:
Various formal languages are studied and their relation, definitions and characterizations are explored. The correspondence between languages and automata is examined.

Expanded Course Description:

  1. Chomsky hierarch, relation between classes of languages
  2. Deterministic context-free languages LR(0) and LR(k) grammars
  3. Context-sensitive languages, linear bounded automata
  4. Closure properties of families of languages, abstract families of languages
  5. Special topics
    1. Indexed grammars
    2. L-systems
    3. Tree automata
    4. Others
  6. Reading of classical and current research papers

Textbook:
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Chapters 9-11, 14.

Instructors: P. Linz

THIS COURSE DOES NOT DUPLICATE ANY EXISTING COURSES

Back to Course Descriptions