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

### Like this:

Like Loading...

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.