User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      