Prove that L = {0 x 1 y 2 x+y | x >= 0 and y >=1} is not Regular. Must use Closu

ID: 3731140 • Letter: P

Question

Prove that

L = {0x 1y 2x+y | x >= 0 and y >=1} is not Regular.

Must use Closure(s).

[ Describe the language in English first ]

Hint: Your "destination" should be

{ a^z b^z | z >= 1} = a language with a’s followed by the same number of b’s, which we know is not Regular.

Start with L

(show a sequence of operations and results)

1. Describe Operation Result

End with {a^z b^z} which is not regular

2. Conclusion about L:

ANSWER:

Here in the given language,

number of 0's + number of 1's = number of 2's

along with that each string from language belongs to language 0*1*2* .

i.e each string has sequence of characters in the order 0000.. 111... and then 222..

here 0,1 and 2 can be repeated in string any number of times with condition that ,

number of 0's + number of 1's = number of 2's.

lets say ,

number of 0's + number of 1's = number of 2's = z.

Hence each string from language is of the form a^zb^z

where a = 00..11..= sequence of 0's followed by sequence of 1's

and b = 22... = sequence of 2's

z = number of elements in each .

Here, given language also has form of a^zb^z which is not regular

Hence given language is not regular.

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