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
asked Feb 16 "17 at 7:53

73166 silver- badges1818 bronze title
include a comment |

1 answer 1

active oldest Votes
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$.

edited Feb 16 "17 at 9:12
reply Feb 16 "17 in ~ 8:06

1,19077 silver- badges1111 bronze badges
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

Post together a guest

email Required, however never shown

Post together a guest


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
prove a language is not continuous using pumping lemma
making use of the pumping Lemma come prove a language is not regular.
show that the language $w in a,b^* : #w_b = #w_a + 2 $ is not constant using the pump Lemma
prove language is not consistent using pump lemma
Prove that the language together is no a consistent language, using pumping lemma
utilizing Pumping Lemma prove that the language $L = a^ib^j mid i,j in N $ is no Regular.
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.


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.