CS 373: Introduction to Theory of Computation

Fall 2010

The final exam will be cumulative, but will concentrate on the material covered since the second midterm (namely, on grammars which is roughly in chapter 2 of the textbook). Key skills that will be tested in the final include the skill sets for midterm 1 and midterm 2, and in addition, the following new material:

• 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; check if a given input string belongs to the language defined by a CFG using the CYK algorithm.
  • 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.