CS341 Automata TheoryFinal Exam Review Sheet - Solutions1. For each of the following languages, determine if the language is (I) regular, (II)context-free but not regular, (III) not context-free. Prove your answer.(a) L = {anbn+2|n ≥ 0}(II) CF, not regularCF: S → aSb|bbnot regular: Apply pumping lemma to w = apbp+2and pump either way.(b) L = {xay|x, y ∈ {a, b}+}(I) This language contains all strings over {a, b} that have length of at least 3 andcontain at least one a other than the first and last symbols. (a ∪ b)+a(a ∪ b)+(c) L = {0n1m+n2m+n|m, n ≥ 0}(III) not CF. Apply pumping lemma to w = 0p12p22p2. Give both a CFG and a PDA for the following languages.(a) L = {akc3br|r > k}CFG: S → aSb|BB → bB|bCC → ccc(b) L = {w ∈ {0, 1}∗|w = wR}This solution should be in your class notes.S → 0S0|1S1|ǫ|0|1For the PDA: In start state p, push 0s and 1s on the stack. Use an epsilontransition to move to final state q - in state q, pop the symbol (0 or 1) that youread.(c) L = {w ∈ {a, b}∗||w| is odd and the middle symbol of w is a}We did this PDA in class.For the CFG: S → aSb|aSa|bSb|bSa|a3. Give a regular expression and a FA for the following languages.(a) L = {w ∈ {0 , 1}∗|wbegins with a 1 and ends with a 0}Regular expression: 1(0 ∪ 1)∗0(b) L = {w ∈ {0, 1}∗|w contains substrings 010 and 101}Regular expression: (0 ∪ 1)∗010(0 ∪ 1)∗101(0 ∪ 1)∗∪ (0 ∪ 1)∗101(0 ∪ 1)∗010(0 ∪1)∗∪ (0 ∪ 1)∗0101(0 ∪ 1)∗∪ (0 ∪ 1)∗1010(0 ∪ 1)∗4. Give the state diagram of a recognizer for the following.(a) L = {aibicj|i, j ≥ 0, j > i}1(b) L = {0n12n+1|n ≥ 0}5. Define a TM that computes the function f where f (x) = 2x + 1.TM R on input 0i:1. If there are no 0s on the tape, write a 0 and halt.2. Mark the leftmost 0 with an X, scan right and overwrite the first blank with a Y. 3.Move left to the leftmost 0, and goto step 2. If there are no more 0s on the tape, thenscan the tape, over-writing all X’s and Y’s with 0s. 4. Over-write t he leftmost blankwith a 0 and halt.6. Prove that the decidable languages are closed under complement.Let L be a decidable language. Assume TM T decides L. We will define a TM S thatdecides Lc.TM S on input w:1. Run T on w. If T accepts w, reject. If T rejects w, accept.7. Prove that L = {< M > | M is a TM and M accepts a ll strings of length less than 5in 100 steps or less} is decidable.We define a decider T f or L.TM T on input < M > where M is a TM:1. Enumerate all strings of length 4 or less over M’s alphabet: s1, s2, ..., sk.2. Run M for 100 steps on each string s1, s2, ..., sk. If M accepts all these strings,accept. Otherwise, reject.8. Assuming only that AT Mis not decidable, prove that HALTT Mis not decidable.Assume BWO C that HALTT Mis decidable, and that TM T decides it. We will use Tto construct a decider S for AT M.TM S on < M, w >, where M is a TM a nd w is a string:1. Run T on < M, w >. If T rejects, then M do es not halt on w, and therefore M doesnot accept w, so reject.If T accepts < M, w >, then M halts on w, so r un M on w: if M accepts w, accept; ifM rejects w, reject.9. Prove that L = {< M > |M is a TM and if M accepts any string w, then M alsoaccepts wr} is not decidable.Assume BWOC that L is decidable. So some TM T decides it. We will use T to builda decider S for AT M.First we show how, given an input < M, w > for S, to construct an input < M′> forT, such that:< M, w >∈ AT M↔< M′>∈ L, i.e., M accepts w if and only if whenever < M′>accepts a string t, it accepts tR.TM M′on input x:1. If x = 0 1, accept.22. If x 6= 10, reject.3. If x = 1 0, run M on w. If M accepts w, accept.So if M accepts w, then the L(M′) = {01, 10}, and if M does not accept w, L(M′) ={01}.TM S on input < M, w >, where M is a TM and w is a string:1. Construct M′from M and w.2. Run T on < M′>. If T accepts, accept. If T rejects, reject.So S decides AT M. Contradiction.10. Prove the f ollowing lanuages are SD but not decidable:(a) L = {< M > |M is a TM and M accepts at least 2 strings }L is SD - the following TM recognizes L:TM R on input < M >, where M is a TM:1. Enumerate the strings over M’s input alphabet: s1, s2, s3, .....2. For i = 1, 2, 3, 4, ...:2a. Run M for i steps on s1, ..., si. If M accepts two or more of these strings, accept.L is not decidable.We did this reduction proof in class, except that < M > was in L if M acceptedat least 3 strings (instead of 2 ) .(b) L = {< M1, M2> |M1, M2are TMs and aa ∈ L(M1) ∪ L(M2)}We did this proof in class, if you replace the string aa with
View Full Document
Unlocking...