Using theorems 3.5.2 and 3.5.3 in the text, or the pumping lemma game for context-free languages, show that the following language is not context-free: {wcwcw: w elementof {a, b}*}. Just like the pumping theorem for regular languages (Theorem 2.4.1), this theorem is useful for showing that certain languages are not context-free. For example, L = {a^n b^n c^n: n greaterthanorequalto 0} is not. For suppose that L = L(G) for some context-free grammar G = (V, sigma, R, S). Let n > phi (G)^|V - sigma|/3. Then w = a^n b^n c^n is in L(G) and has a representation w = uvxyz such that v or y is nonempty and uv^n xy^n z is in L (G) for each n = 0, 1, 2, ... There are two cases, both leading to a contradiction. If vy contains occurrences of all three symbols a, b, c, then at least one of v, y must contain occurrences of at least two of them. But then uv^2 xy^2 z contains two out occurrences out of their correct order a b before an a, or a c before an a or b. If vy contains occurrences of some but not all of the three symbols, then uv^2 xy^2 z has unequal numbers of a' s, b' s, and c' s. L = {a^n: n greaterthanorequalto 1 is a prime} is not context-free. To see this take a prime p greater than phi (G)^|V - sigma|, where G = (V, sigma, R, S) is the context-free grammar allegedly generating L. Then w = a^p can be written as prescribed by the theorem, w = uvxyz, where all components of w are strings of a's and vy notequalto e. Suppose that vy = a^q, and uxz = a^r, where p an q are natural numbers, and q > 0. Then the theorem states that r + nq is a prime, for all n greaterthanorequalto 0. This was found absurd in Example 2.4.3. It was no accident that, in our proof that {a^n: n greaterthanorequalto 1 is a prime} is not context-free, we resorted to an argument very similar to that in Example 2.4.3, showing that the same language is not regular. It turns out that any context-free language over a single-letter alphabet is regular; thus, the result of the present example follows immediately from this fact and Example 2.4.3. Using theorems 3.5.2 and 3.5.3 in the text, or the pumping lemma game for context-free languages, show that the following language is not context-free: {wcwcw: w elementof {a, b}*}. Just like the pumping theorem for regular languages (Theorem 2.4.1), this theorem is useful for showing that certain languages are not context-free. For example, L = {a^n b^n c^n: n greaterthanorequalto 0} is not. For suppose that L = L(G) for some context-free grammar G = (V, sigma, R, S). Let n > phi (G)^|V - sigma|/3. Then w = a^n b^n c^n is in L(G) and has a representation w = uvxyz such that v or y is nonempty and uv^n xy^n z is in L (G) for each n = 0, 1, 2, ... There are two cases, both leading to a contradiction. If vy contains occurrences of all three symbols a, b, c, then at least one of v, y must contain occurrences of at least two of them. But then uv^2 xy^2 z contains two out occurrences out of their correct order a b before an a, or a c before an a or b. If vy contains occurrences of some but not all of the three symbols, then uv^2 xy^2 z has unequal numbers of a' s, b' s, and c' s. L = {a^n: n greaterthanorequalto 1 is a prime} is not context-free. To see this take a prime p greater than phi (G)^|V - sigma|, where G = (V, sigma, R, S) is the context-free grammar allegedly generating L. Then w = a^p can be written as prescribed by the theorem, w = uvxyz, where all components of w are strings of a's and vy notequalto e. Suppose that vy = a^q, and uxz = a^r, where p an q are natural numbers, and q > 0. Then the theorem states that r + nq is a prime, for all n greaterthanorequalto 0. This was found absurd in Example 2.4.3. It was no accident that, in our proof that {a^n: n greaterthanorequalto 1 is a prime} is not context-free, we resorted to an argument very similar to that in Example 2.4.3, showing that the same language is not regular. It turns out that any context-free language over a single-letter alphabet is regular; thus, the result of the present example follows immediately from this fact and Example 2.4.3