[an error occurred while processing this directive]

MTH210

Tutorial 9

Ryerson University
[an error occurred while processing this directive]

(none)

[an error occurred while processing this directive]

FSA's and The Pumping Lemma

[an error occurred while processing this directive]

(none)

[an error occurred while processing this directive]

Due: (none)


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