CS341 Automata Theory (Summer 2008)Homework Assignment ♯4Do not forget to write your name and EID.1. Define the language t hat is generated by each of the following context-free grammars:(a) S → aSa|bSb|a|b.(b) S → aS|bS|ε.(c) S → aS|Sb|ε.2. For each of the following languages L, construct a context-free gra mmar that generatesit:(a) {anbm|m ≥ n, m − n is even}.(b) {xcn|x ∈ {a, b}∗, ♯a(x) = n or ♯b(x) = n}.(c) {xcn|x ∈ {a, b}∗, ♯a(x) + ♯b(x) ≥ n}.(d) {aibj|2i = 3j + 1}.3. Construct pushdown automata that accept each of the following languages:(a) L = {ambn| m ≤ n ≤ 2m}.(b) L = {w ∈ {a, b}∗| w has twice as many a’s as b’s}.(c) L = {ambn| m ≥ n}.4. For each o f the following languages, each one is either (I) regular, (II) context-free butnot regular, or (III) not context-free. Decide to which category each language belongsand prove your answer.(a) L = {aibn|i, n 6= 0, i = n or i = 2n}.(b) L = {xy| x, y ∈ {a, b}∗, |x| = |y|}.(c) L = {0i1j|j = i2}(d) L = {x1#x2#x3...#xk|k ≥ 2, xi∈ {a, b}∗∀i, and xi= xjfor some i 6= j}(e) L = {0n#02n#03n|n ≥ 0}5. Consider L = {0i1i|i ≥ 0}. What is wrong with the following proof that L is notregular? Describe the problem clearly, and correct the proof.Assume BWOC that L is regular, and let p be the pumping length. Choo se w = 0p1p.So w ∈ L a nd |w| ≥ p. So the pumping lemma tells us that w = xyz such that |xy| ≤ p,|y| > 0, and xyiz ∈ L for all i ≥ 0.1Since |xy| ≤ p, it follows thatx = 0i, y = 0j, z = 0p−i−j1pwhere j > 0.Let j = 1. Then xz = xy0z = 0p−11p, and so the #0(xz) 6= #1(xz). So xz 6∈ L.Contradiction! So L is not
View Full Document
Unlocking...