5. Use the pumping 1emma for regular languages to prove that the language L give

Question

5. Use the pumping 1emma for regular languages to prove that the language L given below is not regular. The alphabet of L is = { a, b, c} L-{ci bj an I j > 0, i 2 0 and i + j > m } You may write your proof in your preferred pr format , but your oof must precisely specify the information required for each of the five blanks in the following template. Note that the third blank requires an integer as an exponent. Use p as the pumping length. Define all variables that you use in your proof. contradicts the pumping lemma because for all x, y, z eT* and xy-z is not Proof. The sentence s= such that xyz-s, if (xyl Sp and lyl>0, then y must be in L because QED You need to use the following concepts for problems 6 - 7 strings x and y are distinguishable with respect to a language L if there is a string d such that one of the strings xd and yd is a sentence in L but the other is not. The string d is known as a distinguisher for x and y. A set of strings are pair-wise distinguishable if there is a distinguisher for each pair of strings in the set. 6. Show a set of 3 strings that are pairwise distinguishable with respect to the language I given in problem 5. Make the 3 strings as short as possible. For each pair of the 3 strings, give a distinguisher Minimum State Lemma. Ifthere are k pairwise distinguishable strings with respect to a or more states. 7. Use the Minimum State Lemma given above to show that the language L given in problem 5 is not regular, by finding an infinite set D of strings that are pairwise distinguishable with respect to L. Define the set D precisely and show a distinguisher for each pair of strings in the set D

Explanation / Answer

Solution:

Note: More than one question asked.

5.

Let s=bp-3a4, such that length of s is greater than p. Here i=0 , j=p-3 and m=4

and p-3>4.

Then y must be “ba” and xy2z=babaa4, which is not in L since b comes after a.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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