Write 250–500 words (1) summarzing her talk using the vocabulary of CS 301, (2) saying whether you agree with her overall and why.

The remaining questions are intended to be a sample final exam covering all the material in the course excluding Chapter 7. It is intended to take about 2 hours, just like the real final. The real final exam will have about 10-20% of its points devoted to material from Chapter 7.

- Show that LR = {<M> : M is a TM that accepts w^R whenever it accepts w} is undecidable.
- For each of the following languages, identify whether it is regular, context-free but not regular, decidable but not context free, Turing-recognizable but not decidable, or not Turing-recognizable. If it's regular, give a DFA, NFA, or regular expression. If it's context-free, give a PDA or CFG. If it's decidable, sketch the algorithm. If it's Turing-recognizable, describe (in English) how to recognize it. Furthermore, for context-free languages, also prove the language is not regular. For Turing-recognizable languages, prove the language is not decidable (without using Rice's theorem). For languages that are not Turing-recognizable, prove that they are not turing Recognziable.
- L1 = {wx: |w|=2·|x| and w∈a+b+ and x∈a+b+}
- L2 = {<M>: M rejects at least two even length strings}
- L3 = {xyx^R : x is a nonempty string of 0's and 1's and y is arbitrary string of 0's and 1's}
- L4 = {<M> : L(M) is not regular}

- Give an example of:
- A language that is co-Turing-recognizable but not Turing-recognizable.
- A language that is enumerable, but not enumerable in lexicographic order.
- Two languages L1 and L2 such that L1 mapping reducest to L2, and L1 is decidable, and L2 is undecidable. (Please briefly describe the reduction.)

- Draw a state diagram of a DFA for the set of all strings over {a,b} that do not contain either the substring ab or the substring ba.
- Draw a state diagram of an NFA
*with exactly five states*for the set of all strings over {0, 1} that do contain the substring 0101.

This topic: CS301 > WebHome > Syllabus > Homeworks > ProblemSet12

Topic revision: r2 - 2012-04-17 - 03:42:02 - Main.sloan

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |