CSCI 2670

Test 2 Guide

Fall 2013
Test 2 will cover material from Chapters 2, 3 and 4 (and related slides). An understanding of Chapters 0 and 1 will be assumed and will be needed to answer certain questions. The test will be closed book and closed notes, and calculators and other electronic devices may not be used.
Some questions on the test will be short answer—e.g., given a list, you might be asked to identify elements possessing a certain property, and you might be asked to give a justification for your answer. Some questions might require writing paragraphs—e.g., a proof, or a description of a Turing machine’s behavior. Others will involve constructing an object that satisfies a given requirement (e.g., provide CFG for a given language; provide an implementation level description of a TM that decides a given language), or converting from one model to another (e.g., from CFG to CNF).

The following are among the tasks you might be asked to perform.
1. Use pumping lemma to prove a language is not context free.
2. Given a description of a context-free language L, provide a context free grammar(CFG) G such that L(G) = L.
3. Convert a CFG into Chomsky Normal Form (CNF).
4. Given a CFG G, create a push-down automaton (PDA) that accepts L(G).
5. Given the description of a language or problem, provide an implementation level description of a Turing machine to solve the problem. That is, use English prose to describe the TM and its behavior, referencing its parts.
6. Given the description of a language or problem, provide a high level description of a Turing machine to solve the problem. That is, use English prose to