(a) L = {w#w R#w | w ∈ {0,1}

CSCE 4115/5400 ASSIGNMENT #5 SOLUTION
1. Prove that the following are not context-free languages.
(a) L = {w#wR #w | w ∈ {0, 1}∗ }. Example strings in L include 01#10#01, 110#011#110,
and 000#000#000.
Let z = 0n #0n #0n . z ∈ L. According to the pumping lemma, z = uvwxy such
that |vx| ≤ n and uvi wxi y ∈ L. Clearly neither v nor x may contain a # and
be pumped to get a string in L. If v and x contain only 0’s, then these 0’s
are from 2 adjacent sets only, not all 3 sets. Therefore, pumping v and x
will give a string with a different number of 0’s in one or two sets but not
the third and so the string would not be in L. Hence, L is not context-free.
(b) L = {bn #bm #bn×m | bi is i in binary, i ≥ 1}. Example strings in this language include
10#11#110, 111#100#11100, and 101#110#10110.
Note that multiplying by any binary number b by 10n give b0n−1 (e.g., 101×
10n = 1010n−1 . Let z = 1n #10n #1n 0n−1 . z ∈ L. According to the pumping lemma,
z = uvwxy such that |vx| ≤ n and uvi wxi y ∈ L. Clearly neither v nor x may contain
a # and be pumped to get a string in L. In fact, the only sets of strings
which may be pumped to get a string in L would have v from the 1’s in the
first string and x from the 1’s in the 3rd string, or v from the 0’s in the
second string and x from the 0’s in the third string. In the first case,
this is not possible because this would require vwx to span 1n #10n #1n , which
cannot be done with |vwx| ≤ n. In the second case, this is not possible because
this would require vwx to span 0n #1n 0n−1 , which cannot be done with |vwx| ≤
n. Therefore, there are no choices of v and x from string z which may be
pumped to get a string in L. Hence, L is not context-free.
(c) L = {w | w is a string of the form (0∗ 1)∗ , with all sets of 0’s the same length}. The
strings of this language are ε, 0101, 001001, 00010001, ....
Let z = 0n 10n 10n . By the pumping lemma, z may be rewritten as uvwxy such that
1 ≤ |vx| ≤ n and uwy is in L. It is obvious that neither v nor x can contain
1. If vx contains only 0’s in one or even two of the 3 sets of 0’s, uwy will
not be in L. Gi ven the length of vx, it cannot span all 3 sets of 0’s. Hence,
L is not context-free.
2. Consider the grammar G with productions as follows:
S → AS | AB | a
A→b
B → SC
C → DS
D→c
Use the CYK algorithm to test membership of babaca.
S, B
B
S
A
b
S
a
S
A
b
S
a
C
D
c
S
a
Since S cannot derive the string, the string is not in L (G).

Download Report