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
\$endgroup\$
include a comment |

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
\$endgroup\$
include a comment |

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.

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

Draft saved

authorize up making use of Facebook
submit

### Post together a guest

surname
email Required, however never shown

### Post together a guest

surname
email

Required, however never shown

## 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

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