Test #2 Topics
The test covers Chapters 2 and 3 in the textbook.
Chapter 2 - Context-Free Languages
- Know the formal definition of a context-free grammar and the
language of a grammar.
- Be able to write a derivation of a string if given a grammar;
be able to construct a parse tree representing the derivation of
a string in a grammar. Know what a leftmost derivation is.
- Know what it means for a string to have an ambiguous derivation;
know what it means for a grammar to be ambiguous.
- Be able to design a context-free grammar for a given context-free
language.
- Given a grammar and a language be able to prove the grammar
generates the language (if it does) OR find a counterexample to
show it doesn't generate the language (if it doesn't).
- Know what Chomsky Normal form is.
- Know the formal definition of a pushdown automaton.
- Given a context-free language, be able to construct a pushdown automaton
to accept it. Be able to show that your PDA works.
- Given a PDA be able to trace its computation (on a specific string
or in general) and determine what language it accepts.
- Know the relationship between PDAs and Context-Free grammars. Be able
to construct a PDA from a grammar using the technique in the proof
of Lemma 2.21 and show a trace of its computation on a string.
- Know the relationship between regular languages and context-free
languages. Know the relationship between DFAs and grammars.
- Know the closure properties for context-free languages; that is,
which operations is the class of context-free languages closed under
and which is it not. Be able to prove closure properties.
- Know the Pumping Lemma for Context-Free Languages and be able to
use it to prove a language is not context-free. Understand where
the pumping length in the lemma comes from.
Chapter 3 - The Church-Turing Thesis
- Know the definition of a Turing Machine.
- Know what a configuration of a Turing Machine is and, using the
notation from the book, trace the computation of a Turing machine on
given input by showing the sequence of configurations.
- Know the difference between a Turing machine recognizing
a language and deciding a language.
Know what it means for a language to be Turing-recognizable;
know what it means for a language to be Turing-decidable.
- Be able to construct a Turing Machine to recognize a given
language. Be able to do this both at the "implementation" level
giving a description of what the Turing machine would do; be able
to do it more formally constructing a state diagram to show
the transition function.
- Know what a multitape Turing machine is; be able to design
multitape Turing machine to recognize (or decide) a language.
- Be able to give a general description of how a multitape
Turing machine can be simulated on a single-tape Turing machine.
- Know what a nondeterministic Turing machine is; be able to
design one to recognize (or decide) a language.
- Be able to give a general description of how a 3-tape
Turing machine can simulate a nondeterministic Turing machine.
- Know what an enumerator is; be able to design one to enumerate
a Turing-recognizable language.
- Understand the relationship between enumerators and Turing
machines.
- Understand how to generate a sequence of strings in lexicographic
order; understand how this was used in the 3-tape Turing machine
that simulates a nondeterministic Turing machine and how it was used
to list all strings over the alphabet in constructing an enumerator
from a Turing machine.
- Know what the Church-Turing Thesis is.