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:
    1. 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
    2. Push down automata, deterministic push down automata
    3. Linear bounded automata
    4. 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
    1. Can you decide if a language (given by an arbitrary f.a., for example) is empty
    2. Can you decide if a given cfg generates the empty language
    3. Can you decide if two finite automata generate the same language
    4. 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)