HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
midregularlanguageprovepumpingusinglemmage0not

Problem

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular.

This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider any pumping decomposition $w = xyz$ such that $|y| >0$ and $|xy| \le p$.

I'm not sure what to do next.

Am I on the right track? Or am I way off?

Solution

Hint: You need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things $x$, $y$ and $z$ can be given that $xyz=(01)^p2^p$. Then you pump each one and see whether you get a contradiction, which will be a word not in your language. Each case needs to lead to a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

Of course, you need to work through the details and consider all the possible splittings.

Context

StackExchange Computer Science Q#1027, answer score: 6

Revisions (0)

No revisions yet.