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.

(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?

(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).

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.

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 {aⁿ bⁿ cⁿ : n  0}, is not context-free, prove that c.f.l.'s are NOT closed under complement or intersection.

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?

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.

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

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)³.

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?

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 H₁ and the complement of H₁? Reference: these are defined on p. 252 of the text).
7. Prove that H₁ is Turing-acceptable.
8. Prove that the complement of H₁ is not Turing-acceptable.
9. What is The Halting Problem? Know that The Halting Problem is undecidable.

1. Understand the proofs from Theorem 6.3.1 of the old text or Theorem 5.4.2 of the new one.
2. Be able to distinguish between solvable and unsolvable problems.
3. Be able to design algorithms for solvable problems.
4. Be able to prove that a problem is unsolvable by reducing a problem known to be unsolvable to it.