Scribd Logo
Upload

Welcome to Scribd!

  • 71 views

    Pumping Lemma Writeup

    Uploaded by

    rimi
    The document proves that the language L={0n: n is a perfect square} is irregular by contradiction. It assumes L is regular and applies the pumping lemma. It chooses the string w=0n2, where n is the pumping constant. It partitions w as xyz such that |xy|<=n and pumps y twice, obtaining a string xy2z not in L since its length is not a perfect square. This contradicts the pumping lemma, so L must be irregular.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Pumping Lemma Writeup

    Uploaded by

    rimi
    71 views3 pages
    The document proves that the language L={0n: n is a perfect square} is irregular by contradiction. It assumes L is regular and applies the pumping lemma. It chooses the string w=0n2, where n is the pumping constant. It partitions w as xyz such that |xy|<=n and pumps y twice, obtaining a string xy2z not in L since its length is not a perfect square. This contradicts the pumping lemma, so L must be irregular.

    Original Description:

    pumping lemma examples

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document proves that the language L={0n: n is a perfect square} is irregular by contradiction. It assumes L is regular and applies the pumping lemma. It chooses the string w=0n2, where n is the pumping constant. It partitions w as xyz such that |xy|<=n and pumps y twice, obtaining a string xy2z not in L since its length is not a perfect square. This contradicts the pumping lemma, so L must be irregular.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    71 views3 pages

    Pumping Lemma Writeup

    Uploaded by

    rimi
    The document proves that the language L={0n: n is a perfect square} is irregular by contradiction. It assumes L is regular and applies the pumping lemma. It chooses the string w=0n2, where n is the pumping constant. It partitions w as xyz such that |xy|<=n and pumps y twice, obtaining a string xy2z not in L since its length is not a perfect square. This contradicts the pumping lemma, so L must be irregular.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    CS311 Winter 05 Ammara Shabbir

    Prove that Language L = {0n: n is a perfect square} is irregular.

    Solution:

    L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer
    n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such
    that:

    |y| > 0 , |xy| <= n and for all k>=0 , the string xykz is also in L.

    Choose w to be w = 0s where s = n2 that is it is a perfect square.

    Let w= 00000000000000000………00000 = xyz . (The length of w = s = n2 in this case.)


    Let |xy| <= n and |y| = k.

    That is w = 0000 0k 000…


    X y z

    So, |xyz| = |xz| + |y| = (n2- k ) + (k)


    From pumping lemma, I can pump y any number of times and the new string should also belong
    to the language. Suppose I pump y twice then, the new string should belong to the language that
    is it should have length that is a perfect square but,

    |xy2z| = |xz| + 2|y| = (n2- k ) + 2k = n2 + k

    where n2 + k < n2 + n (k <= n as |xy| <=n and |y| = k )


    < n2 + 2n +1
    = (n+1)(n+1)

    and n2 + k > n2 (As k > 0)

    => n2 < n2 + k < (n+1)2

    Ö n2 + k is not a perfect square


    Ö xy2z is not in L
    Ö This is a contradiction to the pumping lemma
    Ö So, our initial assumption must have been wrong that is L is not regular.

    1
    CS311 Winter 05 Ammara Shabbir

    Prove that Language L = {0n: n is a perfect cube} is irregular.

    Solution:

    L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer
    n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such
    that:

    |y| > 0, |xy| <= n and for all k>=0 , the string xykz is also in L.

    Choose w to be w = 0s where s = n3 that is it is a perfect square.

    Let w= 00000000000000000………00000 = xyz . (The length of w = s = n3 in this case.)


    Let |xy| <= n and |y| = k.

    That is w = 0000 0k 000…


    X y z

    So, |xyz| = |xz| + |y| = (n3- k ) + (k)


    From pumping lemma, I can pump y any number of times and the new string should also belong
    to the language. Suppose I pump y twice then, the new string should belong to the language that
    is it should have length that is a perfect cube but ,

    |xy2z| = |xz| + 2|y| = (n3- k ) + 2k = n3 + k

    where n3 + k < n3 + n (k <= n as |xy| <=n and |y| = k )


    < n3 + 3 n2 + 3n +1
    = (n+1)3

    and n3 + k > n3 (As k > 0)

    => n3 < n3 + k < (n+1)3

    Ö n3 + k is not a perfect cube


    Ö xy2z is not in L
    Ö This is a contradiction to the pumping lemma
    Ö So, our initial assumption must have been wrong that is L is not regular.

    2
    CS311 Winter 05 Ammara Shabbir

    Steps to solve Pumping Lemma problems:


    1. If the language is finite, it is regular (quiz3-section1), otherwise it might be non-regular.
    2. Consider the given language to be regular
    3. State pumping lemma
    4. Choose a string w from language, choose smartly :`)
    5. Partition it according to constraints of pumping lemma in a generic way
    6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
    given.
    7. State the contradiction and end the proof.

    How to remember what pumping Lemma says:


    (As ahsan mentioned)

    Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
    “there exists”. Notice:

    For every regular language L


    There exists a constant n
    For every string w in L such that |w| >= n,
    There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and
    For every k>=0 , the string xykz is also in L.

    What does this imply?


    Ö I can choose the language I want to prove (this is trivial…obviously in exams you have no
    choice but you can pick up a language of choice during practice)
    Ö I cannot choose n that is I have to keep it arbitrary; I have to use a generic value. (So I
    cannot choose 4 or 16 as the length of my string It has to be defined as a function of n)
    Ö I can choose w, with any combination of alphabets. The only constraint is that the
    chosen string should belong to the language under consideration. (So I can have
    000000… or 111111 … or the combination of the two even if the alphabet comprises of any
    number of letters in the first or second solution as long as length chosen arbitrarily is perfect
    square…but I cannot have all aaaaa… in anbn language since it does not belong to the
    language.. I can choose only those strings that conform to the language’s general
    construction)
    Ö I cannot choose the division of my string. It has to be arbitrary and general and should
    conform to the pumping lemma constraints. (SO, I cannot choose the length of y to be 1 or
    2 It has to be a generic, choose a variable k or something)
    Ö I can choose my pumping factor k. (This means that I can choose to pump any number of
    times I want to. I can choose to pump 0 times 1 time or even put a constraint on it like I have
    not pumped more than n times like sir did in class in the factorial proof). If you want to
    complete a proof your pumpimg factor should lead to a contradiction to pumping
    lemma but the point is you can pump any times you want like in prime language proof
    in the book you could have pumped p-m times or 2p-2m times or 3p-3m times …no
    constraint there.

    I hope this helps in clarifying confusions!!

    You might also like