Let M be the pump length and also let S be a cable in $A_1$ such that $|S|geq M$, therefore let $$S=0^M1^M2^M$$

Because that the pumping lemma, we can divide S into three pieces xyz, therefore let $S=xyz$ where $|y|>0$ and also $|xy|leq M$.

You are watching: Use the pumping lemma to show that the following languages are not regular.

Let $xy=0^M$ and $z=1^M2^M$, therefore we have the right to say $x=0^M-1$ and $y=0$.

Since the pumping lemma says that any kind of $xy^izin A$ where $igeq 0$, climate $xy^2zin A$. Therefore,

$$0^M-10^21^M2^M=0^M+11^M2^Min A_1$$

Which is a contradiction come the original language. Therefore, $A_1$ is not regular.

Ho does the look?. This is my very first proof through the pump lemma.


proof-verification computer-science regular-language pumping-lemma
share
mention
monitor
asked Feb 16 "17 at 7:53
*

danieldaniel
73166 silver- badges1818 bronze title
$endgroup$
include a comment |

1 answer 1


active oldest Votes
1
$egingroup$
Looks good otherwise, except you need to show that over there is no eligible $xyz$ division. You"ve only shown that $x = 0^M-1$ and $y = 0$ is not eligible. Editing and enhancing the proof isn"t difficult though, just let $x = 0^M-n-k, y = 0^n, z = 0^k 1^M 2^M$ where $M geq n > 0$.


share
cite
monitor
edited Feb 16 "17 at 9:12
reply Feb 16 "17 in ~ 8:06
*

kviirikviiri
1,19077 silver- badges1111 bronze badges
$endgroup$
include a comment |

her Answer


Thanks for contributing response to stillproud.orgematics Stack Exchange!

Please be certain to answer the question. Provide details and share her research!

But avoid

Asking for help, clarification, or responding to various other answers.Making statements based upon opinion; ago them up with referrals or personal experience.

Use stillproud.orgJax to style equations. stillproud.orgJax reference.

To find out more, view our advice on writing great answers.

See more: The 24 Motives 24 Names Blank, The Peters Chuen E Mann — 24 Motives 24 Names


Draft saved
Draft discarded

Sign increase or log in


authorize up utilizing Google
authorize up making use of Facebook
sign up utilizing Email and also Password
submit

Post together a guest


surname
email Required, however never shown


Post together a guest


surname
email

Required, however never shown


short article Your prize Discard

By clicking “Post her Answer”, friend agree to our regards to service, privacy policy and cookie plan


Not the prize you're looking for? Browse various other questions tagged proof-verification computer-science regular-language pumping-lemma or ask your very own question.


Featured top top Meta
connected
1
prove a language is not continuous using pumping lemma
0
making use of the pumping Lemma come prove a language is not regular.
1
show that the language $w in a,b^* : #w_b = #w_a + 2 $ is not constant using the pump Lemma
0
prove language is not consistent using pump lemma
0
Prove that the language together is no a consistent language, using pumping lemma
2
utilizing Pumping Lemma prove that the language $L = a^ib^j mid i,j in N $ is no Regular.
0
pumping Lemma - Grammar - regular language
warm Network concerns much more hot inquiries

inquiry feed
subscribe to RSS
inquiry feed To subscribe to this RSS feed, copy and also paste this URL right into your RSS reader.


*

stillproud.org
agency
ridge Exchange Network
site design / logo design © 2021 ridge Exchange Inc; user contributions licensed under cc by-sa. Rev2021.10.27.40576


stillproud.orgematics stack Exchange works best with JavaScript enabled
*

your privacy

By click “Accept all cookies”, girlfriend agree stack Exchange can store cookies on your machine and disclose information in accordance through our Cookie Policy.