For a non-deterministic finite automaton over an alphabet , we write for the set of words accepted by . We write for the length of the word , and write for the set of non-negative integers.
Answer the following questions:
(1) Consider the non-deterministic finite automaton depicted below, where is the start state, and is the only final state. Give that satisfy all of the following conditions:
(i)
(ii)
(iii) for every .
(2) Prove that, for every non-deterministic finite automaton consisting of states and for every such that , there exist and that satisfy all of the following conditions:
(i)
(ii)
(iii)
(iv) for every .
(3) Prove that there exists no non-deterministic finite automaton such that . You may use the fact proved in question (2).
Classic proof of Pumping Lemma (PL) for regular languages.
Let be an automaton with states.
Let such that .
Now let's simulate run of of word .
Define states .
That is, is a state in which is after reading first inputs.
From pigeonhole principle, at lest two of those state must be exactly the same state.
Let be the state that is visited the second time for the first time (i.e. is the smallest among all such states).
I claim that: , where
Obviously, because and .
States create a loop in the automaton - it can be traversed any number of times, thus .
For we simply "skip" the loop, for we traverse the loop times.
Assume that is regular language.
Then pumping lemma must hold.
Consider , where is the pumping lemma constant.
Because , then there must exist a partitioning
such that , and \textbf{for all} .
Notice that consists of 's only.
Let's "pump up" .
For example, contains of significantly more 's than 's.
This word does not belong to the language.
Contradiction with statement that for all .
is not regular, thus there exist no automaton recognizing it.
