CS 373: Introduction to Theory of Computation
Spring 2013
The second midterm will cover material from lecture 12 through
lecture 17 (on pumping lemma and non context-free languages). 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: context-free grammars; 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.