GentleRex
Induction example
Intro to Theory of Computation
Reg lang properties
Pumping Lemma
decidability and MORE..
   
 



Pumping lemma

What is the pumping lemma and why do we care?

Pumping lemma is a means of making the distinction between regular and non-regular languages

Essentially we are hand-simulating the dfa loop.

A few things to keep in mind before looking at specifics:

The pumping lemma is only used to prove nonregularity in languages.

you might ask : 'how do i prove a language is regular'? no known theorem - you don't need one - as you can prove regularity by writing a dfa/nfa/ regular expression to express the language.

Another big issue here is that at times (with tricky languages) you can actually 'pump' non-regular languages - in certain places and do so successfully. This does not violate the pumping lemma as you may (at times) have to be careful about which substring you pump.


Here is an example problem for pumping lemma:


{ 1n0n, where n > 0} (better expressed as 'n' 1's followed by 'n' 0's  or equal number of 1's followed by equal number of 0's)

Is easy (ier) to demonstrate pumping lemma

 to disqualify it as a regular language

Consider    =>   111000

 

You cannot 'pump' 11 or 00 so you choose '10'

substring as likely candidate.

11  10   00

 

 

Replacing with

11 '1010' 00

 

If you 'pump' y 2x

 

There! You have violated pumping lemma

 thus demonstrating non-regularity

 

Course example includes

 

{ languages over (0,1) with equal number of zeros and ones}

 

The same example actually 'pumps' to a correct solution

  - this does not prove correct it just fails at disproving…

 

Actually what you are doing in this case is producing a

word that is different in pattern than the last but

 (luckily…for the string is not you….) does not violate

the language description.

 

Consider in the second mentioned language that the

following strings exist

0011

000111

00001111

0000011111

000000111111

 

And so on …

Just as

0101101011001100

From which you could 'pump' and get an

appropriate solution  - but , not the same pattern

 so you only proved part of the language.

 

Perhaps a better explanation is that you should

 be able to pump (and reverse pump) a large

 enough example

 

I cannot reverse pump or decompose the 0011, 000111…

pattern as I would break the pattern from all 0's to all

 1's and these are (although not all of the language

DO exist in my language of equal number 1's and 0's. )

 

 

With the second language 'D' mentioned on pp 77

 (equal number '01' and '10' substrings……)

Includes 0110, 01011010, 0110011010100101

  you can decompose all of these examples

 (provided they are big enough  - you will find

the appropriate substrings that can be pumped

Ie.

 

 

'01100110'     '1010'  '0101'   ''

X,                      y1,        y2,        z

 

Correspondingly I can 'pump' up a smaller example to

 ANY of the larger…                                                                                           

 







Pumping lemma chronicals – part two
Use CF-PL to show {ww | where w  is comprised of {0.1}* }
NOTE: we know this

1.) for each I > = 0 ,
u x  z within A

2.) |uy| > 0 and
3.) |vxy| <= p.


Meaning what ?


'z' is the only variable that can be specified as empty string – or least allow any utility towards a solution in this capacity….

Because we know we won't solve anything (prove) by setting v or y to null (note: at least one must be non-null) but the true power that gave us a larger set of languages was the fact that we could  pump in two areas (representing the power that we utilized the 'stack' to represent)  - so we won't set either to null… it just wont produce a meaningful solution.


For part two , vxy have to be less than or equal to p (really no meaningful case would consider that they are equal for that would be imply that y was null – again not supporting a meaning ful way of proving anything here – since  you are negating the power of the two area pump which gave us more power than the one area pump on the RE-lp!

 

Pp 127 considers o to power p as w.

With


An example


                                  Mid
          |
                                 V

U                  v     x          y     z  
000…000     0     1          0    000…0001

 

Your familiar with reg-PL, so you know where this is going … (it will be skewed thus not 'pumping' correctly….)


Not as exemplary as considering our 'friend' (or so we might think) 'x' which could be 'null'

 


You might fool friends and neighbors if they haven't been brushing up on automata lately if you suggested that 'x' could be null  - but when you reduce z you still need x  - here you could make it look solvable by setting z as only one character and balancing it with x as one character


                                  Mid
          |
                                 V

V                       x          y                        z  
000…000          1          0 000…000       1


Got rid of 'u' (it can be empty remember?)

Now you have completely fooled someone into thinking that you can pump this to an equivalent language.


It works for 00000010000001    !


And many others (a lot!)


However, there are cases where it still doesn't work!


Consider

000011111 000011111


One can argue "hey I can pump to the proposed suggestion and still fit the language!" yes, but
It is not the same pattern and cannot be reverse pumped (ie broken down , when large enough)

As 'w' in the above case can be pumped…


From 0000 1111  1
With 00001111 as v
To 0000111100001111


But I cannot be pumped to

0000000011111111 1

Or as ww together  would look like


0000000011111111 1  0000000011111111 1

Likewise, I cannot break down this example to copies of
V and y as they cannot be pumped in that fashion


The string

0000000011111111 1  0000000011111111 1

Is in the language

{ww | where w  is comprised of {0.1}* }

And it cannot be solved with CF-PL


If I cannot solve it with one then it is not CF!


Done.