This homework assignment has 3 problems worth a total of 20 points. Problem 1 involves constructing a context-free grammar and pushdown automaton for a language of balanced strings. Problem 2 proves that a certain language involving strings with balanced 0s and 1s is not context-free using the pumping lemma. Problem 3 also uses the pumping lemma to prove that a language involving concatenating strings with their reversals and themselves is not context-free.
This homework assignment has 3 problems worth a total of 20 points. Problem 1 involves constructing a context-free grammar and pushdown automaton for a language of balanced strings. Problem 2 proves that a certain language involving strings with balanced 0s and 1s is not context-free using the pumping lemma. Problem 3 also uses the pumping lemma to prove that a language involving concatenating strings with their reversals and themselves is not context-free.
This homework assignment has 3 problems worth a total of 20 points. Problem 1 involves constructing a context-free grammar and pushdown automaton for a language of balanced strings. Problem 2 proves that a certain language involving strings with balanced 0s and 1s is not context-free using the pumping lemma. Problem 3 also uses the pumping lemma to prove that a language involving concatenating strings with their reversals and themselves is not context-free.
This homework assignment has 3 problems worth a total of 20 points. Problem 1 involves constructing a context-free grammar and pushdown automaton for a language of balanced strings. Problem 2 proves that a certain language involving strings with balanced 0s and 1s is not context-free using the pumping lemma. Problem 3 also uses the pumping lemma to prove that a language involving concatenating strings with their reversals and themselves is not context-free.
This homework has a total of 3 problems on 2 pages. Solutions should be submitted to Canvas before 3:00pm on Friday Oct 19. The problem set is marked out of 20, you can earn up to 1 + 8 + 6 + 6 = 21 points. Please refer to the homework guidelines for formatting as well as policy on late days. If you choose not to submit a typed write-up, please write neat and legibly. Collaboration is allowed/encouraged on problems, however each student must independently com- plete their own write-up, and list all collaborators. No credit will be given to solutions obtained verbatim from the Internet or other sources.
1. (8 points) Consider the language
L = {w ∈ {0, 1}∗ |w = Reverse (w)}
(a) (3 points) give a context free grammar for this language.
SOLUTION:
s→ (1) s→0 (2) s→1 (3) s → 0s0 (4) s → 1s1 (5)
(b) (5 points) convert this CFG to an equivalent PDA.
SOLUTION:
1 0, → 0 1, → 1
, → $ start q0 q1
, → 0, → 1, →
q3 q2 , $ →
0, 0 → 1, 1 →
2. (6 points) Prove that the language
L = 0i 1j 0i |i ≤ j
is not context-free. SOLUTION: Let p be the length provided by the CFG pumping lemma. Consider the string
0p 1p 0p ,
and suppose it’s written as
uvxyz with |vxy| < p and |vy| > 0. If either v or y contain a 1, it means vxy can only contain 0s from one of the sides. Then uxz is not in the language because the number of 1s decreases but one side of 0s remains the same. Otherwise v and x must contain all 0s. Then pumping once,
uv 2 xy 2 z
gives a string with too many 0s.
3. (6 points)
2 Prove that the language
L = {w ◦ Reverse (w) ◦ w |w ∈ {0, 1}∗ }
is not context-free. Note that while we showed in class that the language {ww : w ∈ {0, 1}∗ } is non-context-free, a minor modification to Problem 1 from this homework can show that {w ◦ Reverse(w) : w ∈ {0, 1}∗ } is context-free. So the last copy of w is crucial for this problem. SOLUTION: The proof is by contradiction. Suppose L is context-free, then let p be the pumping length given by the pumping lemma for context free languages. Consider the string w = 0p 10p , which gives the string s = 0p 102p 102p 10p ∈ L in the language. Consider a decomposition of s into uvxyz. |uvx| ≤ p, it can contain at most one 1. If one of v or y contains this 1, then pumping once gives a number of 1s not a multiple of 3. Thus vy must consist of entirely 0s. Then consider pumping with i = 2, aka the string
uv 2 xy 2 z
Because each interval of 0s has length at least p, pumping v and y can change the sizes of at most two adjacent groups of 0s. Furthermore, because |vy| > 0, this pump must change the length of at least one group of 0s. However, the positions of the 1s dictate how the string must fold onto itself. That is, we must have uv 2 xy 2 z = ŵ3 where ŵ = 0i 10j for some values of i and j. The resulting string is in turn
3 (a) vy touches the first and second groups of 0s, then the 3rd and 4th group imply 2i = 2p and j = p, which implies ŵ = w, a contradiction with the increase in total length. (b) vy touches the second and third groups, then the first and last group imply i = j = p, which again gives a contradiction. (c) vy touches the third and fourth groups, then the first and second group imply i = p and 2j = 2p, again a contradiction by via ŵ = w.
