MTH210 |
Tutorial 9 | |
FSA's and The Pumping Lemma |
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.
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.