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)