My Math Forum Automata Question

 Computer Science Computer Science Forum

 November 1st, 2015, 03:34 AM #1 Newbie   Joined: Oct 2015 From: Iran Posts: 7 Thanks: 1 Math Focus: Mathematical Logic , Computation Theory Automata Question Can you prove that this RE : 0^n1^n can't make a regular Language ? With Pumping Lemma !
 November 7th, 2015, 11:26 PM #2 Newbie   Joined: Nov 2015 From: Singapore Posts: 12 Thanks: 6 Math Focus: Computer Science, Mathematics, Statistics suppose RE is regular, by pumping lemma, there exists $\displaystyle p\geq 1$ such that for all $\displaystyle w \in RE, |w|\geq p \implies$ there exist a decomposition w=xyz such that $\displaystyle |xy|\leq p , |y|\geq 1 \text{ and }xy^iz \in RE \text{ for all i>0 }$ We can challenge whoever claim that it is a regular language to choose a p. Given this p, we have the freedom to choose any arbitrary w with length $\displaystyle |w|\geq p$ in this case, given any p, we choose $\displaystyle w=0^p1^p$ this forces $\displaystyle xy=0^k, \text{ for some }k\leq p \text{ since }|xy|\leq p$ and hence, y =$\displaystyle 0^m,\text{ for some }m\geq 1$ now, consider $\displaystyle xy^2z=0^{p+m}1^p \notin RE$ hence a contradiction which proofs that RE cannot be a regular language
 November 8th, 2015, 01:42 AM #3 Newbie   Joined: Nov 2015 From: Singapore Posts: 12 Thanks: 6 Math Focus: Computer Science, Mathematics, Statistics Actually this isn't a good problem to start off with as you can practically choose w to be anything but your proof will be longer to consider the various cases. For your understanding, let's consider a separate problem where the choice of w is crucial. I would like to encourage you to think of proving a language to be irregular as a game between you and someone who wants to claim that it is regular. step 1: you challenge your opponent to select a number p such that pumping lemma holds. step 2: you carefully select a w (so that you can win the game) step 3: your opponent finds a prefix xy of w (w=xyz) and denote which part of the prefix is the part where we can pump. His choice is restricted by the fact that the length of xy |xy|<=p step 4: now you find a k such that $\displaystyle xy^kz$ is not in the language, usually k=2 works. as a demonstration, i shall define another language $\displaystyle L=\{0^m1^n|n>m\}$ and prove it is not regular. step 1: let him select a p for which he thinks his pumping lemma will hold. step 2: you select w to be $\displaystyle 0^p1^{p+1}$ check that |w|=2p >=p step 3: you will find that as usual, no matter how your opponent choose, the prefix must be of the form $\displaystyle 0^i$ and therefore his y must also be of the form $\displaystyle 0^j$ and $\displaystyle z=0^{p-i}1^{p+1}$ step 4: $\displaystyle xy^2z=0^{i-j}0^{2j}0^{p-i}1^{p+1}=0^{p+j}1^{p+1}$ but p+j>=p+1 means that $\displaystyle xy^2z \notin L$ which is well and good and you win. suppose instead at step 2 we are careless and choose w to be $\displaystyle 0^{p-1}1^{p}$ now his turn in step 3, he can actually choose $\displaystyle xy=0^{p-1}1, |xy|=p,y=1$ now, no matter what k you choose,$\displaystyle xy^kz=0^{p-1}1^{p+k}\in L$. He'd be happy he won the game, but this doesn't mean that L is actually regular, he is just lucky that you have not chosen the right w. So the idea behind using pumping lemma is to choose the w to force the choice by your opponent so that you win no matter what he choose. Now as an exercise, go back to the original question and see why I said that any choice of w with length |w|>=p works. Last edited by changcw83; November 8th, 2015 at 01:50 AM.

 Tags automata, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post taih Applied Math 1 December 22nd, 2013 12:17 PM riow Applied Math 0 October 14th, 2013 09:03 PM BenFRayfield Number Theory 0 July 30th, 2013 08:32 AM MrPhil Computer Science 0 August 30th, 2012 11:48 PM Phrzby Phil Computer Science 0 June 12th, 2007 11:02 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top