For the following language, identify whether or not it is regular and prove your

Question

For the following language, identify whether or not it is regular and prove your assertion. When it is not regular, use Game with the Demon. Dont apply the Pumping Lemma directly. L = { x e {a, b, c)" | x is a palindrom. } Games with the Demon Like its regular cousin, the pumping lemma for CFLs is most usefnl in its contrapositive form. In this form, it states that in order to conclude that A is not context-free, it suffices to establish the following property: For all k 2 0, there exists z e A of length at least k such that for all ways of breaking z up into substrings z uvwxy with and |vwxl 0, and lvwl3k 4. You pick i 2 0. If uv'wr'y A, then you win. If you want to show that a given set A is not context-free, it suffices to show that you have a winning strategy in this game; that is, no matter what the demon does in steps 1 and 3, you have moves in steps 2 and 4 that can beat him

Explanation / Answer

Solution:

Note: The proof is for regular language.

The steps of the game with demons are given below:

L= {x | x (a, b, c)*, x is a palindrome}

some of the strings in the language are

aca, aacaa, abcba, c, aabcbaa

This is a contradiction which means the given language L is not regular.

similarly, the other languages can also be proved,

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---