Guide to Exam 2
Instructions
Exaam 2 will be held during the class time on Thursday, March 21, starting at 6:10 pm and lasting for 100 minutes - until 7:50 pm. There will be a brief review time before the exam. After a 10 minutes break we will have one hour of lecture.
The exam is open book - you may use your notes, homeworks, any handouts and solutions you have worked out, the text (Sipser), and any other paper-based references. You may not use any electronic devices, such as laptops, phones, or tablets.
Write your answers in the blue books provided. Show all your work and indicate your final answers clearly.
General things to know
Context-free grammars, leftmost derivations, parse trees, ambiguity
Pushdown automata and Turing machines: state transitions diagrams and informal descriptions.
Mutli-tape and/or non-deterministic Turing machines: informal descriptions.
Context-free languages, decidable languages, Turing-recognizable languages.
Closure (and non-closure) properties of context-free, decidable languages, and Turing-recognizable languages:
CFLs closed under union, conatenation, star, and intersection with regular language; not closed under complement and intersection.
decicable languages closed under complement, intersection, union, conatenation, and star.
Turing-recognizable languages closed under union, intersection, conatenation, and star, not closed under complement.
Equivalence of context-free languages, context-free grammars, and PDAs.
That any regular language is context-free.
Pumping Lemma for context-free languages.
Turing machines: deciders vs. recognizers.
Decidable languages vs. Turing-recognizable languages.
Specific things you should know how to do:
Given a CFG and a string, be able to create a derivation and/or parse tree for that string.
Given an NFA be able to create a corresponding PDA.
Given a description of a language (e.g. in English, as a set, or in the form of a regular expression), be able to construct:
A CFG that generates it.
A PDA that recognizes it.
A TM that decides it.
Given a DFA, be able to create a corresponding TM.
Be able to apply the Pumping Lemma for CFG’s to prove that a language is not context-free.
Be able to apply the colsure properties of context-free languages to prove a language is or is not context-free.
In addition you should undertsnd the basic idea behind the proof of the Pumping Lemma for context-free languages: that a parse tree for context=free languages must be tall enough to have a path guaranteed to contain repeated variables.