Homework 16 Languages That Are and Are Not Context Free 1 CS 341 Homework 16 Languages that Are and Are Not Context-Free 1. Show that the following languages are context-free. You can do this by writing a context free grammar or a PDA, or you can use the closure theorems for context-free languages. For example, you could show that L is the union of two simpler context-free languages. (a) L = ancbn (b) L = {a, b}* - {anbn : n ≥ 0} (c) L = {ambncpdq : n = q, or m ≤ p or m + n = p + q} (d) L = {a, b}* - L1, where L1 is the language {babaabaaab…ban-1banb : n n ≥ 1}. 2. Show that the following languages are not context-free. (a) L = {an2 : n ≥ 0} (b) L = {www : w ∈ {a, b}*} (c) L = {w ∈ {a, b, c}* : w has equal numbers of a's, b's, and c's} (d) L = {anbman : n ≥ m} (e) L = {anbmcnd(n+m) : m, n ≥ 0} 3. Give an example of a context free language ( ≠ Σ*) that contains a subset that is not context free. Describe the subset. 4. What is wrong with the following "proof" that anb2nan is context free? (1) Both {anbn : n ≥ 0} and {bnan : n ≥ 0} are context free. (2) anb2nan = {anbn}{bnan } (3) Since the context free languages are closed under concatenation, anb2nan is context free. 5. Consider the following context free grammar: G = ({S, A, a, b}, {a, b}, R, S), where R = { S → aAS S → a A → SbA A → SS A → ba } (a) Answer each of the following questions True or False: (i) From the fact that G is context free, it follows that there is no regular expression for L(G). (ii) L(G) contains no strings of length 3. (iii) For any string w ∈ L(G), there exists u, v, x, y, z such that w = uvxyz, |vy| ≥ 1, and uvnxynz ∈ L(G) for all n ≥ 0. (iv) If there exist languages L1 and L2 such that L(G) = L1 ∪ L2, then L1 and L2 must both be context free. (v) The language (L(G))R is context free. (b) Give a leftmost derivation according to G of aaaabaa. (c) Give the parse tree corresponding to the derivation in (b). (d) Give a nondeterministic PDA that accepts L(G). 6. Show that the following language is context free: L = {xxRyyRzzR : x, y, z ∈ {a, b}*}.Homework 16 Languages That Are and Are Not Context Free 2 7. Suppose that L is context free and R is regular. (a) Is L - R necessarily context free? (b) Is R - L necessarily context free? 8. Let L1 = {anbm : n ≥ m}. Let R1 = {(a ∪ b)* : there is an odd number of a's and an even number of b's}. Show a pda that accepts L1 ∩ R1. Solutions 1. (a) L = ancbn. We can easily do this one by building a CFG for L. Our CFG is almost the same as the one we did in class for anbn: S → aSB S → c (b) L = {a, b}* - {anbn : n ≥ 0}. In other words, we’ve got the complement of anbn. So we look at how a string could fail to be in anbn. There are two ways: either the a’s and b’s are out of order or there are not equal numbers of them. So our language L is the union of two other languages: • L1 = (a ∪ b)* - a*b* (strings where the a’s and b’s are out of order) • L2 = anbm n ≠ m (strings where the a’s and b’s are in order but there aren’t matching numbers of them) L1 is context free. We gave a context-free grammar for it in class (Lecture 12). L2 is the complement of the regular language a*b*, so it is also regular and thus context free. Since the union of two context-free languages is context free, L is context free. (c) L = {ambncpdq : n = q or m ≤ p or m + n = p + q}. This one looks scary, but it’s just the union of three quite simple context-free languages: L1 = ambncpdq : n = q L2 = ambncpdq : m ≤ p L3 =ambncpdq : m + n = p + q You can easily write context-free grammars for each of these languages. (d) L = {a, b}* - L1, where L1 is the language {babaabaaab…ban-1banb : n n ≥ 1}. This one is interesting. L1 is not context free. But its complement L is. There are two ways to show this: 1. We could build a PDA. We can’t build a PDA for L1: if we count the first group of a’s then we’ll need to pop them to match against the second. But then what do we do for the third? L is easier though. We don’t need to check that all the a groups are right. We simply have to find one that is wrong. We can do that with a nondeterministic pda P. P goes through the string making sure that the basic b(a+b)+ structure is followed. Also, it nondeterministically chooses one group of a’s to count. It then checks that the following group does not contain one more a. If any branch succeeds (i.e., it finds a mismatched pair of adjacent a groups) then P accepts. 2. We could use the same technique we used in (b) and (c) and decompose L into the union of two simpler languages. Just as we did in (b), we ask how a string could fail to be in L1 and thus be in L. The answer is that it could fail to have the correct b(a+b)+ structure or it could have regions of a’s that don’t follow the rule that each region must contain one more a than did its predecessor. Thus L is the union of two languages: • L2 = (a ∪ b)* - b(a+b)+ • L3 = {xbambanby ∈ {a, b}* : m+1 ≠ n}. It’s easy to show that L2 is context free: Since b(a+b)+ is regular its complement is regular and thus context free. L3 is also context free. You can build either a CFG or a PDA for it. It’s very similar to the simpler language anbm n ≠ m that we used in (b) above. So L1 = L2 ∪ L3 is context free. 2. (a) L = {an2 : n ≥ 0}. Suppose L = {an2 : n ≥ 0} were context free. Then we could pump. Let n = M2. So w is the string with M22, or M4, a's.) Clearly |w| ≥ K, since M > K. So uvvxyyz must be in L (whatever v and yHomework 16 Languages That Are and Are Not Context Free 3 are). But it can't be. Why not? Given our w, the next element of L is the string with (M2+1)2 …
View Full Document
Unlocking...