CS341 Automata TheoryMidterm 2 ReviewCovered topics include:All material on CFLs: CFGs, PDAs, Chomsky Normal Form, ambiguity of a grammar,closure properties of a CFL,decision procedures for CFLs, pumping lemma for CFLs,conversion of a CFG to a PDA.TMs: definition of semi-decidable/decidable languages, configurations o f a TM, definingrecognizers a nd deciders, defining TM that computes a function on integers.1. For each of the following languages, state whether the language is (I) regular, (II)context-free but not regular, or (III) not context-free. Prove your answer.(a) {0n02n03n|n ≥ 0}(b) {xwxR|x, w ∈ {0, 1}+}(c) {xyz|x, y, z ∈ {0, 1}∗, |x| = |z| > 0 and #0(x) ≥ #0(z)}(d) {1n2|n ≥ 0}(e) L(11(01 ∪ 0)∗(01 ∪ 0) ∪ 10)(f) {w#wR|w ∈ {a, b}∗}(g) {w|w ∈ {a, b}∗, w 6= wR}(h) {aibjck|i < j → k < j}2. Prove that the context-free languages are closed under union and concatenation. (Don’tcopy your class notes - this should be g ood practice for proving a closure pro perty onthe exam).3. Suppose L1, L2are context-free languages. Is it necessarily true that L1−L2is cont ext-free? Prove your answer.4. Convert the following grammar to Chomsky Normal Form. S → A|BA → aA|aCB → bB|bCC → pqrWW → T VT → t|epsilon5. Show that the following CFG is ambiguous:E → E + E|E − E|ExE|(E)|a|b.6. For CFG G and string w, give an algorithm to decide if w ∈ L(G).7. Define a PDA that recognizes {0nw1m|w ∈ {0, 1}∗, #0(w) = #1(w) and m ≥ n}.18. Define a CFG for L = {anbm|n 6= m}.9. Define a recognizer for:(a) L = {anbmcm}(b) L = {w ∈ {0, 1}∗|#0(w) = 2 #1(w)}(c) L = {tat|t ∈ {b, c}∗}10. For the languages in the previous problem, are they: (I) regular, (II) context-free butnot regular, (III) semi-decidable but not context-free? Prove your
View Full Document
Unlocking...