CS 301, Spring 2012, Problem Set 12

1. Listen to the keynote at the 28th Chaos Computer Congress (28C3) from December 2011 by Meredith Patterson on entitled The Science of Insecurity. It runs one hour.

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.

  1. Show that LR = {<M> : M is a TM that accepts w^R whenever it accepts w} is undecidable.
  2. 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.
    1. L1 = {wx: |w|=2|x| and w∈a+b+ and x∈a+b+}
    2. L2 = {<M>: M rejects at least two even length strings}
    3. 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}
    4. L4 = {<M> : L(M) is not regular}
  3. Give an example of:
    1. A language that is co-Turing-recognizable but not Turing-recognizable.
    2. A language that is enumerable, but not enumerable in lexicographic order.
    3. 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.)
  4. 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.
  5. 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.
-- Main.sloan - 2012-04-15
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
Helping Women Faculty Advance
Funded by NSF