Kursangebote im Herbst 2014 - heide-schaefer-design

Found. of Computer Science Theory: Homework 9
Due: Monday, December 8, 2014, beginning of class
• You only have to explain your answer if this is stated in the question.
1. (5 points) Fill out the table from question 1 of the sample final questions.
2. (4 points) Draw a Venn diagram that shows the relationships among the following
classes of languages:
(a) P.
(b) the CFLs.
(c) the decidable languages.
(d) the languages whose complement is Turing-recognizable.
(e) the languages whose complement is decidable.
(f) the regular languages.
(g) the Turing-recognizable languages.
3. (5 points) An unrestricted grammar is like a CFG, except that you can now have any
string in (V ∪ Σ)∗ V (V ∪ Σ)∗ on the left-hand side of a rule. Surprisingly, unrestricted
grammars generate exactly the Turing-recognizable languages. We will not show this,
but we will look at an example.
Given the following grammar, G:
• S → ABaC
• Ba → aaB
• BC → DC
• BC → E
• aD → Da
• AD → AB
• aE → Ea
• AE →
(a) Let L(G) be the language generated by G. Give a description of L(G).
(b) Give a derivation of aaaaaaaa. It is ok to combine very similar steps and write
⇒k when you are taking k very similar steps.
4. (7 points) Consider the following problems:
ALLCFG = { G | G is a CFG and L(G) = Σ∗ }.
⊆CFG,DFA = { G, A | G is a CFG, A is a DFA, and L(G) ⊆ L(A)}.
⊆DFA,CFG = { A, G | A is a DFA, G is a CFG, and L(A) ⊆ L(G)}.
ALLCFG is undecidable (you don’t have to show this).
(a) Show that ⊆CFG,DFA is decidable. Use Sipser notation. Hint: refer to slide 40
from the Lecture21 slides linked to the course schedule, or look at problem 2.18
in Sipser.
(b) Use the undecidability of ALLCFG to show that ⊆DFA,CFG is also undecidable.
Use Sipser notation. Alternatively, it is also acceptable to use the “box inside a
box” visual description we used in class. For either approach, you must clearly
indicate that you are doing a proof by contradiction, and at the conclusion of
your argument indicate the contradiction you have reached.
5. (6 points) Let T = { M | M is a TM that accepts wR whenever it accepts w}.
(a) Can Rice’s Theorem be applied to argue that T is undecidable? Give a brief
explanation for your answer.
(b) Show that T is undecidable using Sipser notation, or using the “box inside a
box” visual description we used in class. For either approach, you must clearly
indicate that you are doing a proof by contradiction, and at the conclusion of
your argument indicate the contradiction you have reached.

Download Report