Description

CSE340: Theory of Computation (Homework Assignment 3)
Total Number of Pages: 1 Total Points 50

Question 1. Design PDAs for the following languages (give the transition diagram only).
(a) (6 points) L1 = {aibjckdl | i = l and i + 2j = 3k + l}.
(b) (8 points) L2 = Σ∗ {ww | w ∈ Σ∗}. Assume that Σ = {a,b}.
Question 2. One of the following two languages is context-free and one is not.
L = {aibjckdl | i = k and j = 2l} M = {aibjckdl | i = k or j = 2l}
(a) (2 points) Which of the above two languages is context-free? (b) (6 points) Give a CFG for the language which is context-free (c) (6 points) Show that the other language is not context-free.
Question 3. Show that the following languages are decidable.
(a) (7 points) L1 = {hMi | M is a DFA which does not accept any string that contains 101 as a substring}
(b) (7 points) L2 = {hR,Si | R,S are regular expressions and L(R) ⊆ L(S)}
Question 4. (8 points) Show that the following language is decidable
L = {hGi | G is a CFG over {0,1}∗ and 1∗ ⊆ L(G)}.
Page 1 of 1