CS 373: Introduction to Theory of Computation

Fall 2012

The second midterm will cover material from lecture 12 through lecture 18 (on Chomsky Normal Form). This corresponds to material in Chapter 2 of the textbook by Sipser (both 2nd and 3rd editions), excluding the formal proof of equivalence between PDAs and CFGs, and deterministic Context-free languages. Key skills that will be tested in the midterm include:

• Formal Definitions:
  • Know the formal definitions of: grammars (type 0, type 1, type 2 (which is context-free), and type 3); derivations; language defined by the grammar; parse tree of a string in a context-free language; ambiguous context-free grammars, and inherently ambiguous context free languages; Chomsky Normal Form for a grammar.
  • For an example grammar, know how to: describe it using formal tuple notation; give a derivation for a given string; draw a parse for a given string; describe the language defined; prove correctness of the language recognized.
  • Know the formal definitions of: a pushdown automaton, computation of a PDA on a given word, when an input string is accepted, and the language recognized/accepted by a PDA.
  • For an example PDA, know how to: describe it formal using tuple notation; describe the computation on a given input string; describe the language accepted by the PDA.
• Grammar/Automata Constructions:
  • Given a set of strings design a grammar/PDA recognizing it.
  • Understand and apply to specific examples the following translations: remove epsilon-productions, unit productions, useless symbols from a given grammar; convert a CFG into Chomsky Normal Form.
  • Learn to describe precisely: transformations on grammars/PDAs to obtain grammar/automata with some special property (like a single accept state) for the same language; transformations on grammars/PDAs to prove a closure property.
• Closure Properties:
  • Know the definitions of various operations on languages: union, intersection, complementation, concatenation, Kleene closure, homomorphic image, inverse homomorphic image. Know how to compute the result of applying these operations on example languages.
  • Understand grammar/PDA transformations used in the proofs of closure properties for CFLs
  • Using closure properties to prove non-context-freeness.
  • Using closure properties to prove context-freeness and other closure properties.
• Non-context-freeness:
  • Ability to distinguish between CFLs and non-CFLs.
  • Ability to prove languages to be non-context-free using either the pumping lemma or closure properties.