My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
November 1st, 2015, 03:34 AM   #1
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 !
Saman Q is offline  
November 7th, 2015, 11:26 PM   #2
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
changcw83 is offline  
November 8th, 2015, 01:42 AM   #3
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.
changcw83 is offline  

  My Math Forum > Science Forums > Computer Science

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

Copyright © 2019 My Math Forum. All rights reserved.