* 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.