* Results related to Pumping Lemma
Theorem. A language accepted by a DFA of states is
- nonempty if and only if accepts a sentence of length less lean .
- infinite if and only if accepts a sentence of length with .
The union of the following languages, , is non-regular, but nevertheless it cannot be proven using pumping lemma.
and either , , or
and precisely of symbols in are 3’s
* Regular languages are precisely constant-space languages
Theorem. A regular language can be recognized by a two-way read-only Turing machine.
Proof sketch. Record the configuration of each time we first visit the -th cell. Define a finite automaton to simulate the same behavior.
Theorem. is the same as , both are the class of regular languages. That is, having an algorithm that uses -space is equal to not using any space.
Proof sketch. If a Turing machine uses space, there are possible configurations and possible crossing sequences. If then there are two crossing sequences that are the same, and we can further shorten a shortest string accepted by the machine by the following lemma:
Lemma. Let be a machine and be the input. Suppose two crossing sequence and are equal; then by removing the substring of from index to (assume ), we get another string that is accepted by the machine .
This is a contradiction.
The following language is non-regular but can be decided in space:
where is the binary representation of .
* Generating function of regular language
For a given language ,
is the generating function of . Using analytic combinatorics we can prove the following useful facts.
Theorem. For a regular language , the generating function is rational.
Theorem. Let be a finite automaton of a language . Then the generating function of is the following rational function determined under matrix form
where number of different labels between and ; and as characteristic vectors.
* Minimizing finite automata
Brzozowski’s algorithm use only power set construction and edge reversal . One can observe that reversing edges of a DFA gives an NFA of the reverse language. Then the power set construction gives a minimum DFA. This algorithm takes exponential time in the worst case.
Hopcroft’s algorithm is the fastest algorithm known; runs in time. Try to partition the states using the Myhill-Nerode equivalence relation.
* Relation with
Theorem. and are incomparable.
Proof. Parity is not in . Palindrome/addition/ are not regular.