You should scan and submit this assignment on Blackboard as a pdf. There are fre

Question

You should scan and submit this assignment on Blackboard as a pdf. There are free scanners available in the JPL. Pumping Lemma for CFG For each of the following languages, either show that it is context free by giving a CFG for the language or show it is not context free by using the pumping lemma: {(01)^i2^i|i greater than equal to zero 0} {w | the # of 0s in w = the # of 1s in w = the # of 2s in w} {0^i #0^j#0^i*j |i, j greater than equal to 0} {0^i #0^j #0^i + j |i, j greater than equal to 0}

Explanation / Answer

Statement: every string s in L that has a length of p or more symbols (i.e. with |s| p) can be written as
s = uvwxy
with substrings u, v, w, x and y, such that

1. |vwx| p,

2. |vx| 1, and

3. uvnwxny is in L for all n 0.

Solution:

a. (01)i2i is clearly CFG (We cannot use pumping lemma to prove that the language is Context Free)
CFG:
S --> | A2
A-> 01 | 01A2

b. The language described in statement 2 is too complex to be context-free :P Anyway, we can say 0i1i2i is a subset of the given language. If we can prove that 0i1i2i is not context-free, we can say that the original language is not context-free

suppose i = 2, therefore the word is 001122

let u = <null>, v = 0, w=<null>, x=1, y=22
         uv3wx3y is 00011122 which is not a valid word.

Therefore 0i1i2i is not context free and therefore the language described in statement 2 is also not context free

c.we can prove that 0i1j2i*j is not context-free,

suppose i = 2, j = 2, therefore the word is 00112222

let u = 0, v = 0, w=1, x=1, y=2222
         uv3wx3y is 000011112222 which is not a valid word.

suppose i = 2, j = 1, therefore the word is 00122

let u = 0, v = 01, w=<null>, x=2, y=2
         uv2wx2y is 00101222 which is not a valid word.

Therefore the grammar is not CFG

d. The grammar is CFG
S --> #A | 0S0
A --> # | 0A0

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.