patternMinor
Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular
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?
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.
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.