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^nn>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^{pi}1^{p+1}$ step 4: $\displaystyle xy^2z=0^{ij}0^{2j}0^{pi}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^{p1}1^{p}$ now his turn in step 3, he can actually choose $\displaystyle xy=0^{p1}1, xy=p,y=1$ now, no matter what k you choose,$\displaystyle xy^kz=0^{p1}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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Automata  a question  taih  Applied Math  1  December 22nd, 2013 12:17 PM 
Generating Finite State Automata  5 Tuple  riow  Applied Math  0  October 14th, 2013 09:03 PM 
Elementary Cellular Automata are just the first layer  BenFRayfield  Number Theory  0  July 30th, 2013 08:32 AM 
Construction of Deterministic Finite Automata  MrPhil  Computer Science  0  August 30th, 2012 11:48 PM 
Linear Bounded Automata  Phrzby Phil  Computer Science  0  June 12th, 2007 11:02 AM 