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)