MTH210

Tutorial 9

Ryerson University

FSA's and The Pumping Lemma


Readings

This tutorial covers material from section 12.2 of the textbook and the Computation handout. Page and exercise numbers are from the course textbook.

Tutorial 9

  1. Recall that for w satisfying the conditions of the pumping lemma, w = xyz, where |xy| &le p and x is the prefix of w which ends in a repeated state q say, y is a substring which returns to q and z is the rest of the string.

    Let L = { x ∈ { a, b }* | x contains the string aa }. It can be shown that any machine which accepts L must have at least 3 states, so the pumping constant for L is 3. The DFA below has 3 states and accepts L.

    Using M, for each w below, explicitly find x, y and z and give w0 and w2. If there are multiple choices for x, y and z, give them all.
    1. w = aaa
    2. w = abbaa
    3. w = bbaa

  2. Clearly explain the mistake in the following proof that L = a*b* is not regular.

    Suppose L is regular, so the Pumping Lemma applies to L. Let p be the pumping constant for L.
    Consider w = abp ∈ L.
    | w | ≥ p, so the pumping lemma applies to w.
    Thus there exist x, y, z ∈ { a, b }* such that w = xyz and 1 ≤ | y | ≤ p.
    Take y = abn (n ≤ p), so x = ε and z = bp-n.
    Now w2 = xy2z = abnabp ∉ L.
    This contradicts the Pumping Lemma and so L is not regular.

  3. p. 762 #37, 38

  4. p. 762 #46, 47

  5. For each of the languages given in p. 763 #51, 52, 53, let p be the pumping constant for the language. In each case provide a string w and an integer n, so that the pumping lemma applies to w and wn is not in the language.


This page is maintained by Peter Danziger.
Last modified Monday, 15-Mar-2010 11:29:23 EDT