Prove that the following language is not regular L2 wu wu

Prove that the following language is not regular: L2 = {wu | wu {a, b}* and |w| = |u|}.

Solution

The Myhill–Nerode theorem can be used to prove thatL is not regular.

Corollary of the theorem is that if a language defines an infinite set where we need to maintain count is not Regular. It is frequently used to prove that a language is not regular.

Every finite set is a Regular set.

Infinite set where we do not need to maintain count is Regular(Since Finite automata does not have memory)

Infinite set where we need to maintain count is not Regular

given language L2 = {wu | wu {a, b}* and |w| = |u|}. is an infinite set

And it is countably infinite.

We need to maintain count i.e. |w| = |u| .So the grammer is not regular.