CS 360 Introduction to the Theory of Computing Spring 2015 Assignment 2 Solutions 1. Give context-free grammars for each of the following languages. You do not need to prove that your grammars are correct. However, if it is too difficult to verify the correctness of your grammars, you may lose points (even if they happen to be correct). You should therefore aim to give the simplest grammars possible, and it may be to your benefit to offer short explanations about how your grammars work. (a) x ∈ {0, 1}∗ : x = x R and the number of 1s in x is divisible by 3 . (b) 0n 1m : m ≤ n ≤ 2m . (c) x ∈ {0, 1}∗ : | x |0 > | x |1 . (Recall that | x |0 denotes the number of 0s in x and | x |1 denotes the number of 1s in x.) Solution. (a) A context-free grammar for the language x ∈ {0, 1}∗ : x = x R and the number of 1s in x is divisible by 3 is as follows: S0 → 0S0 0 1S1 1 0 ε S1 → 0S1 0 1S2 1 1 S2 → 0S2 0 1S0 1 The idea is that Sm generates all strings x ∈ {0, 1}∗ with x = x R for which the number of 1s in x is congruent to k modulo 3. (b) A context-free grammar for the language 0n 1m : m ≤ n ≤ 2m is as follows: S → XS1 ε X → 0 00 (c) A context-free grammar for the language x ∈ {0, 1}∗ : | x |0 > | x |1 is as follows: S → XS X X → Y0Y Y → 0Y1Y 1Y0Y ε The idea behind this grammar is that Y generates strings with | x |0 = | x |1 , so X generates strings with | x |0 = | x |1 + 1. The variable S generates the concatenation of one or more strings generated by X, which gives the language in the problem. 2. Let Σ be an alphabet, and recall that the symmetric difference of two languages A, B ⊆ Σ∗ is defined as def A M B = A∩B ∪ A∩B . (a) Prove that if A ⊆ Σ∗ is a context-free language and B ⊆ Σ∗ is a finite language, then the language A M B is context-free. (b) Give an example of an alphabet Σ, a context-free language A ⊆ Σ∗ , and a regular language B ⊆ Σ∗ for which the language A M B is not context-free. Solution. (a) First, given that B is finite, we have that B is regular, and therefore B is regular as well, because the regular languages are closed under complementation. This implies that A ∩ B is context-free, because the intersection of a context-free language and a regular language is always context-free (as we proved in class). Next, we observe that A ∩ B is contained in B, and is therefore finite. Every finite language is context-free, and therefore A ∩ B context-free. Finally, given that we have proved that both A ∩ B and A ∩ B are context-free, it holds that A M B = A ∩ B ∪ A ∩ B is context-free because the union of two context-free languages is necessarily context-free. (b) We may obtain a suitable example by choosing B = Σ∗ and any context-free language A for which the complement A is not context-free. For instance, we may take Σ = {0, 1} and A = C for C = { 0n 1n 0n : n ∈ N } . We have that A is context-free and B is regular, but A M B = A = C is not context-free. 2 3. Let Σ = {0, 1}. For any two strings x, y ∈ Σ∗ with | x | = |y|, define x ⊕ y ∈ Σ∗ to be the bitwise XOR of x and y. For instance, 00101 ⊕ 10110 = 10011. As you might expect, we define ε ⊕ ε = ε. Suppose A ⊆ {0, 1}∗ is a regular language. Define B ⊆ Σ∗ as n o B = xy R : x, y ∈ Σ∗ , | x | = |y|, and x ⊕ y ∈ A . Prove that B is context-free. If your answer includes the description of a CFG or PDA, you do not need to give a formal proof that the CFG or PDA is correct, but you should explain at a high level how it works. Solution. Because A is regular, there must exist a DFA M = ( Q, Σ, δ, q0 , F ) for A. We will define a grammar G = (V, Σ, R, S) for B as follows. First, define the set V of variables of G as V = { Xq : q ∈ Q }. That is, we will have one variable for each state of M. Let us also take the start variable S of G to be Xq0 . Finally, we must indicate set R of rules for our grammar. For every choice of q ∈ Q we will include the following rules in R: Xq → 0Xδ(q,0) 0 Xq → 1Xδ(q,0) 1 Xq → 0Xδ(q,1) 1 Xq → 1Xδ(q,1) 0. We also include the rule Xq → ε for each accepting state q ∈ F. It is the case that L( G ) = B. The idea is that at every intermediate step in a derivation of a string by G, we will have a string of the form xXq y R where | x | = |y| and x ⊕ y causes M to move from the start state q0 to the state q. This is trivially so for the first step of a derivation when we have just the start variable Xq0 , and the rules listed above allow us to conclude that this is true in general. The very last step of a derivation must be the replacement of a variable Xq by ε, which is only possible when q is an accept state. This guarantees that M must accept the string x ⊕ y, which is equivalent to x ⊕ y ∈ A. An alternative way to answer this question is to design a PDA for B. 3 4. Define a language A ⊆ {0, 1}∗ as follows: A = 0n 1n·m : n, m ∈ N . Prove that A is not context-free. In your proof, you may feel free to make use of the following fact without having to prove it: If n, j, k ∈ N are numbers satisfying n ≥ 2 and 1 ≤ j + k ≤ n, then n2 + j does not evenly divide n3 + k. (It is not hard to prove that this fact is true: give it a shot if you feel like it.) Solution. Assume toward contradiction that A is context-free. By the pumping lemma for contextfree languages, we have that there exists a pumping length p for A. We note that there is no loss of generality in assuming that p ≥ 2—for if a given number q is a pumping length for a given context-free language A, then every number q0 ≥ q trivially satisfies the requirements of being a pumping length for A. Now, let 2 3 w = 0p 1p . We have |w| ≥ p and w ∈ A, and therefore the pumping lemma for context-free languages guarantees us that it is possible to write w = uvxyz in such a way that (i) vy 6= ε, (ii) |vxy| ≤ p, and (iii) uvi xyi z ∈ A for all i ∈ N. We now consider the following cases, one of which must hold: Case 1: one of the two string v or y contains both of the symbols 0 and 1. In this case we have that uv2 xy2 z must contain the substring 10, and therefore this string is not contained in A, which contradicts the pumping lemma’s guarantee that uvi xyi z ∈ A for all i ∈ N. Case 2: v = 0s and y = 0t for some choice of s, t ∈ N. Given that vy 6= ε and |vxy| ≤ p, we must have 1 ≤ s + t ≤ p. Considering i = 2, we have uv2 xy2 z = 0 p 2+j 1p 3 for j = s + t. By the fact stated in the question, it cannot be that p2 + j divides p3 for 1 ≤ j ≤ p, and therefore uv2 xy2 z 6∈ A. This contradicts the pumping lemma’s guarantee that uvi xyi z ∈ A for all i ∈ N. Case 3: v = 1s and y = 1t for some choice of s, t ∈ N. Given that vy 6= ε and |vxy| ≤ p, we must have 1 ≤ s + t ≤ p. Considering i = 2, we have 2 uv2 xy2 z = 0 p 1 p 3 +k for k = s + t. By the fact stated in the question, it cannot be that p2 divides p3 + k for 1 ≤ k ≤ p, and therefore uv2 xy2 z 6∈ A. This contradicts the pumping lemma’s guarantee that uvi xyi z ∈ A for all i ∈ N. 4 Case 4: v = 0 j and y = 1k for some choice of j, k ∈ N. Given that vy 6= ε and |vxy| ≤ p, we must have 1 ≤ j + k ≤ p. Considering i = 2, we have uv2 xy2 z = 0 p 2+j 1p 3 +k for 1 ≤ j + k ≤ p. By the fact stated in the question, it cannot be that p2 + j divides p3 + k for 1 ≤ j + k ≤ p, and therefore uv2 xy2 z 6∈ A. This contradicts the pumping lemma’s guarantee that uvi xyi z ∈ A for all i ∈ N. We have obtained a contradiction in all of the possible cases. This implies that A is not context-free, as required. Proof of the fact stated in the question: To prove the fact stated in the problem, let us assume toward contradiction that n2 + j divides n3 + k evenly. Because 1 ≤ j + k ≤ n, we must have n− n n3 n3 + j n3 + n 1 = 2 ≤ 2 ≤ = n+ . 2 n+1 n +n n +k n n As n ≥ 2, we have that the only integer lying between n − n/(n + 1) and n + 1/n is n, and therefore n3 + j = n. n2 + k This implies n3 + j = n3 + nk, and therefore j = nk. Given that 1 ≤ j + k ≤ n, it follows that 1 ≤ k (n + 1) ≤ n, and so n 1 ≤k≤ . n+1 n+1 There is, however, no integer k satisfying these inequalities, and therefore we have obtained a contradiction, implying that n2 + j cannot divide n3 + k evenly. 5

© Copyright 2021