MTH210 |
Tutorial 9 | |
[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) |
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 = ab^{p} ∈ 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 = ab^{n} (n ≤ p), so
x = ε and z = b^{p-n}.
Now w_{2} = xy^{2}z = ab^{n}ab^{p} ∉ L.
This contradicts the Pumping Lemma and so L is not regular.