Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Lecture#8 (PL)

    Uploaded by

    paid games

    Copyright:

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

    Lecture#8 (PL)

    Uploaded by

    paid games
    4 views12 pages

    Original Title

    Lecture#8(Pl)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Lecture#8 (PL)

    Uploaded by

    paid games

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 12

    The Pumping Lemma

    Infiniteness Test
    The Pumping Lemma
    Nonregular Languages

    1
    The Infiniteness Problem
    • Is a given regular language infinite?
    • Start with a DFA for the language.
    • Key idea: if the DFA has n states, and
    the language contains any string of
    length n or more, then the language is
    infinite.
    • Otherwise, the language is surely finite.
    • Limited to strings of length n -1 or less.
    2
    Proof of Key Idea
    • If an n-state DFA accepts a string w of
    length n or more, then there must be a
    state that appears twice on the path
    labeled w from the start state to a final
    state.
    • Because there are at least n+1 states
    along the path.

    3
    Proof – (2)

    w = xyz

    y
    x z

    Then xyiz is in the language for all i > 0.

    Since y is not ε, we see an infinite


    number of strings in L.
    4
    Infiniteness Test: Finding a Cycle
    1. Eliminate states not reachable from
    the start state.
    2. Eliminate states that do not reach a
    final state.
    3. Test if the remaining transition graph
    has any cycles.

    5
    6
    7
    8
    9
    The Pumping Lemma
    • We have, almost accidentally, proved a
    statement that is quite useful for showing
    certain languages are not regular.
    • Called the pumping lemma for regular
    languages.

    10
    Statement of the Pumping Lemma
    Number of
    For every regular language L states of
    DFA for L
    There is an integer n, such that
    For every string w in L of length > n
    We can write w = xyz such that:
    1. |xy| < n.
    Labels along
    2. |y| > 0. first cycle on
    3. For all i > 0, xyiz is in L. path labeled w
    11
    Example: Use of Pumping Lemma
    • We have claimed {0k1k | k > 1} is not a
    regular language.
    • Suppose it were. Then there would be
    an associated n for the pumping lemma.
    • Let w = 0n1n. We can write w = xyz,
    where x and y consist of 0’s, and y  ε.
    • But then xyyz would be in L, and this
    string has more 0’s than 1’s.
    12

    You might also like