CS154 Spring 2020Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is open book, open notes, you will have at least 24 hours to do the test and upload it using the class homework submission mechanism. (d) Some problems will be dependent on some personal information about you such as your ID, and you will not receive credit if you don't make use of this information correctly. (e) It is 10 problems (3pts each), 6 problems will be on materials since the midterm, 4 problems will be from the topics of the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of the practice midterm.

1. Give an example of an ambiguous grammar. Give an example of string generated by the grammar with two distinct leftmost derivations.
2. Convert the grammar with rules `S -> Aba`, `C->D`, `D ->aab`, `B->Ac`, `E->ghc` to CNF. Assume `S` is the start variable.
3. Consider the grammar with rules `S->AT`, `S->c`, `T->SB`, `A->DD`, `B->b`, `D->a`. Assume `S` is the start variable. Show step-by-step how the CYK algorithm would determine if `aacb` was in the language generated by this grammar.
4. Draw a PDA capable of doing palindrome checking for string over the alphabet {a,b,c}.
5. Prove that CFLs are not closed intersection.
6. Modify the PDA definition so that rather than a machine having one stack it now supports two stacks. Show this model can simulate a Turing Machine and that a Turing Machine can simulate a two stack PDA.
7. Carefully define the class SPACE(f(n)) using offline Turing Machines, so that classes like SPACE(log n) are meaningful. Prove an analog of our linear speed-up theorem for space complexity classes.
8. Define the following concepts and give an example: (a) universal Turing Machine, (b) co-r.e.-complete language, (c) co-NP complete language.
9. Define computation history. Prove `E_{LBA}` is undecidable using a computation history argument.
10. Use Rice's theorem to show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.