CSC 320 Final Exam Aid

# CSC 320: Final Exam Study Aid

This an old final exam study aid that you can use for now as a reading list. Context-Free Grammars

(a) Define a c.f.g.
(b) Be able to find a c.f.g for a simple c.f.l.

Regular Languages and Context-Free Languages

(a) Define a regular grammar.
(b) Be able to find a regular grammar for a regular language.
(c) Be able to find a NDFA for any language generated by a regular grammar.
(d) What is the relationship between c.f.l. and regular languages?
(e) Give an example of a c.f.l. that is not a regular language.

PDA's.

(a) Define a PDA.
(b) Be able to write PDA ``programs'' for accepting simple c.f.l.
(c) Define a configuration of a PDA.
(d) Define ``yields in one step'' for a PDA.
(e) Define L(M) for a PDA M.
(f) Which strings are accepted by a PDA? Which are not accepted?

PDA's and CFG's.

(a) Be able to use construction to find a PDA for a language generated by a c.f.g.
(b) Know that it is possible to find a c.f.g. for a language accepted by a PDA (you do not need to know the construction in this case).

Closure Properties.

1. List 3 properties which are closed for c.f.l.
2. Be able to apply constructions involved in proofs from (1).
3. Know that c.f.l.'s are closed under intersection with a regular language. Be able to apply construction in proof of this result.

Pumping Lemma for CFL's.

1. Know how to create the parse tree of a derivation.
2. State the pumping lemma for c.f.l.
3. Be able to apply the pumping lemma for c.f.l. to prove that a language is not context-free.
4. Given that {an bn cn : n  0}, is not context-free, prove that c.f.l.'s are NOT closed under complement or intersection.

The Definition of a TM.

1. Define a TM, a configuration for a TM, and yields in one step.
2. Define halt and hang. Design a TM which never halts and never hangs.
3. What does it mean for a TM to accept a string w?

Computing with TM's.

1. Define what it means for M to halt on input w.
2. Define what it means for M to hang on input w.
3. Understand unary notation.
4. What does it mean for a TM to be able to compute a function from strings to strings?
5. Define what it means for a TM to decide a language. Look at the definition of decides and then explain how one TM can decide more than one language. Be able to design TM's which decide simple languages.
6. Define Turing-acceptable. Be able to design TM's which accept simple languages.

Combining Turing Machines, More Powerful Turing Machines.

1. Be capable of designing more powerful TM's by combining together simpler TM's. Understand machine schema.

4.5 Extensions of the Turing Machine.

1. Be able to prove that a machine with a two-way infinite tape can be simulated on a standard TM.
2. Understand how a k-tape Turing machine can be simulated on a standard TM.
3. Understand how to represent k-tracks on a one-track tape.
4. Be aware that anything you can do on a modern computer in time T(n) can be simulated on a standard TM in time T(n)3.

Universal Turing Machines.

1. Know that TM's can be encoded in various ways (you do not have to memorize details).
2. What is the input for a UTM when you want to simulate a machine M on input w?
3. How can a UTM be constructed using a 3-tape TM? What is each tape used for?

The Halting Problem.

1. Define unsolvable.
2. Prove every Turing-decidable language is Turing-acceptable.
3. Prove that not every Turing-acceptable language is Turing-decidable.
4. Prove that the class of Turing-decidable languages is closed under complement.
5. Prove that the class of Turing-acceptable languages is not closed under complement.
6. What are H1 and the complement of H1? Reference: these are defined on p. 252 of the text).
7. Prove that H1 is Turing-acceptable.
8. Prove that the complement of H1 is not Turing-acceptable.
9. What is The Halting Problem? Know that The Halting Problem is undecidable.