Suggested Answers to Questions in Midterm Exam 2 CSCI 2670 Introduction to Theory of Computing April 7, 2015 1. (15 Points) Let L = {an bm : m ≥ n ≥ 0}. Give a context-free grammar to define this language. Answer: There are a number of ways to solve this problem. A string an bm , where m ≥ n, can be thought as either an bn bm−n or an bm−n bn , leading to two different CFGs for this language. (1) S → PB P → aP b | B → bB | (2) S → aSb | Sb | 2. (15 Points) Design a PDA (diagram) that recognizes the language L = {an bm : m ≥ n ≥ 0}. Answer: See the diagram. Note that the action b, → is needed in the accept state to accommodate all extra bs. 1 3. (15 Points) Convert the following CFG to an equivalent CFG in the Chomsky normal form using the 4-step process described in the book. The alphabet of the defined language is Σ = {(, )}. P → (P ) | Answer: Step 1: add new start nontermal S: S→P P → (P ) | Step 2: remove -rules: P → : S → P | P → (P ) | ( ) Step 3: remove unit rules: S → P : S → (P ) | ( ) | P → (P ) | ( ) Step 4: adjustment: L→( R →) P0 → PR S → LP 0 | LR | P → LP 0 | LR 2 4. (15 Points) Convert the following CFG to a PDA that recognizes the same language the CFG defines. Using the process described in Theorem 2.20. Note that stack operations can only be either push, pop, or single symbol replacement at the top of stack. P → (P ) | Answer: see the diagram 3 5. (20 Points) Lemma 2.27 gives a procedure to convert a PDA to a CFG that defines the same language recognized by the PDA. (1) Modify the following PDA before the procedure can be applied. (2) Apply the procedure on the modified PDA to obtain a desired CFG. Answer: (1) Lemma 2.27 requires that the PDA should (a) have a single accept state, (b) empty the stack before entering the accept state, and (c) in each transition either push or pop stack (but not both). See the modified PDA in the diagram. (2) Introduce nonterminals XAD , XBC , XEE . The rules are: XAD → XBC XBC → 0XBC 0 | 1XBC 1 | XEE XEE → or after removing all unnecessary , XAD → XBC XBC → 0XBC 0 | 1XBC 1 | XEE XEE → 4 6. (20 Points) Using the context-free pumping lemma to prove that the following language is not context-free. L = {0n 1m 0n : m > n ≥ 0} Proof: Assume L is context-free. Then by the pumping lemma, there is a number p. Let s = 0p 1p+1 0p . The length |s| = 3p + 1 > p. By the lemma, s can be rewritten as w = uvxyz, for some u, v, x, y, z ∈ {0, 1}∗ and |vxy| ≤ q and |vy| > 0 Case 1: vy consists of entirely 0s. Both v and y have to belong to the same group of 0s in s (either the prefix 0p or the suffice 0p ). By the lemma the pumped string uv 2 xy 2 z ∈ L. However, the pumped string has the prefix 0s and suffice 0s out of balance; thus it does not belong to L. Contradiction. Case 2: vy consists of entirely 1s. Both v and y have to belong to the group 1s in s. By the lemma the pumped string uv 0 xy 0 z = uxz ∈ L. However, the pumped string has at most p number of 1s; thus it does not belong to L. Contradiction. Case 3: vy consists of mixed 0s and 1s. (a) If either v or y consists mixed 0s and 1s, by the lemma pumped string uv 2 xy 2 z ∈ L. But it contains the interleaving 0s and 1s then 0s and 1s, not in the format of 0s and 1s and then 0s; thus not belong to L. Contradiction. (b) If v consists of only 0s and y consists of 1s (or the other way around), by the lemma pumped string uv 2 xy 2 z ∈ L. However, the prefix 0s and suffix 0s in the pumped string are out of balance; thus it does not belong to L. Contradiction. Since in all the scenarios, we have logic contradiction, the assumption that L is context-free was incorrect. Therefore, we proved that L is NOT context-free. 5

© Copyright 2021