(a) Prove that the language L = {12/3221} is not regular by using the Pumping Lemma....

Transcribed Image Text:

(a) Prove that the language L₁ = {12/3221} is not regular by using the Pumping Lemma. Use the string 1"2"32" and i = 3 at appropriate points in the proof. (b) Write out the proof of the same result which uses the string 132 and i=0 instead. Which steps are different? Which steps remain the same? (e) There are some errors in the proof below that the language L₂ = {1'2' #32 @2'1'} is not context-free. Find and correct all such errors. The best way to do this is to write out the correct proof, highlighting the differences between the correct proof and the one below. Claim: The language L₂ = {12 #32 @21'} is not context-free. Proof: Assume L2 is regular. Then the Pumping Lemma applics and so for some n1 such that for some w L such that wn, w = xyzuv where • lyzu❘ ≤n ⚫y and uλ ry' zu've L for all i > 0 w= Choose w 12" 32" @2"1" and so we L and w≥n. So by the Pumping Lemma w = xyzuv = 12 #32@2"1" and lyzul <n. This means that y and u can contain at most two of 1, 2 and 3. We will refer to the part of the string before #as zone 1, the part of the string between # and @ as zone 2, and the part of the string after @as zone 3. Now if y or u contains # or @, then clearly ryzuv & L, as this would contain two occurrences of either # or @. Hence neither unor v contains either # or @. Now note that both y and u can only cover at most two of zone 1, zone 2, and zone 3, as yzul <n. This means that ryzuv € L, as one of the zones will have the same string as w, but the other two will have longer strings, and hence ryzuv is not of the form 12 #3202'1'. This is a contradiction, and so L2 is not context-free. (d) Let L be a regular language over the alphabet {0, 1}. Use the Pumping Lemma to show that n≥1 such that for all we L where wn, there is another string such that rЄL and [r] <n. (a) Prove that the language L₁ = {12/3221} is not regular by using the Pumping Lemma. Use the string 1"2"32" and i = 3 at appropriate points in the proof. (b) Write out the proof of the same result which uses the string 132 and i=0 instead. Which steps are different? Which steps remain the same? (e) There are some errors in the proof below that the language L₂ = {1'2' #32 @2'1'} is not context-free. Find and correct all such errors. The best way to do this is to write out the correct proof, highlighting the differences between the correct proof and the one below. Claim: The language L₂ = {12 #32 @21'} is not context-free. Proof: Assume L2 is regular. Then the Pumping Lemma applics and so for some n1 such that for some w L such that wn, w = xyzuv where • lyzu❘ ≤n ⚫y and uλ ry' zu've L for all i > 0 w= Choose w 12" 32" @2"1" and so we L and w≥n. So by the Pumping Lemma w = xyzuv = 12 #32@2"1" and lyzul <n. This means that y and u can contain at most two of 1, 2 and 3. We will refer to the part of the string before #as zone 1, the part of the string between # and @ as zone 2, and the part of the string after @as zone 3. Now if y or u contains # or @, then clearly ryzuv & L, as this would contain two occurrences of either # or @. Hence neither unor v contains either # or @. Now note that both y and u can only cover at most two of zone 1, zone 2, and zone 3, as yzul <n. This means that ryzuv € L, as one of the zones will have the same string as w, but the other two will have longer strings, and hence ryzuv is not of the form 12 #3202'1'. This is a contradiction, and so L2 is not context-free. (d) Let L be a regular language over the alphabet {0, 1}. Use the Pumping Lemma to show that n≥1 such that for all we L where wn, there is another string such that rЄL and [r] <n.

Answer rating: 100% (QA)

SOLUTION A To prove that the language L1 1i 2j 32i 2j 1i is not regular using the Pumping Lemma well assume that L1 is regular and then derive a contradiction Here are the steps of the proof Assume th... View the full answer