# Automata & Formal Languages

## Exam Syllabus

#### Related Courses

- CS 562 Automata Theory
- CS 620A Formal Languages and Syntactic Analysis I

#### References

- Introduction to Automata Theory, Languages, and Computation, Hopcroft and Ullman, Addison-Wesley
- The Theory of Parsing, Translation, and Compiling, Vol I, Aho and Ullman, Prentice-Hall
- Introduction to Formal Language Theory, Harrison, Addison-Wesley
- Theory of Finite Automata with an Intro. to Formal Languages, Carroll and Long Prentice-Hall

#### Topics

- This exam deals with generators and recognizers for various classes of languages
- Grammar types: type 3 (regular), type 2 (context free), type 1(context sensitive), type 0(general)
- In addition the ideas of deterministic and ambiguous context free grammars and languages should be understood (for languages, the term ‘inherent ambiguity’ is used)
- Normal forms: Greibach and Chomsky
- Normal forms for cfl’s
- Recognizers:
- Finite automata, including these variations–non-deterministic finite automata, finite automata with lambda moves, 2-way finite automata with or without end-markers; Equivalence proofs for these models; Mealy and Moore machines plus equivalence proofs
- Push down automata, deterministic push down automata
- Linear bounded automata
- Turing machines

- Equivalence proofs for grammar classes and their corresponding recognizers
- Closure properties for language classes: examples are closure under union, complement, intersection,concatenation, Kleene closure, homomorphism, inverse homomorphism, quotient with arbitrary or regular sets, intersection with a regular set
- Regular expressions and Kleene’s analysis-synthesis theorem
- Right congruence relations, Nerode’s theorem, minimization of finite
- Automata, machine homomorphism for finite automata
- Standard pumping lemmas for type 3 and type 2 languages
- Decidability properties for machines and languages: some examples are
- Can you decide if a language (given by an arbitrary f.a., for example) is empty
- Can you decide if a given cfg generates the empty language
- Can you decide if two finite automata generate the same language
- Can you decide if the intersection of two given cfl’s is empty note: post’s correspondence problem should be understood, but it’s proof need not be learned

- ‘Universal’ Turing machine, undecidability of the halting problem, example of a language that is recursively enumerable but not recursive, diagonalization ideas and proofs
- Proof that every type 1 language is recursive (decidable)