__LANGUAGES RECOGNIZED BY FA.__ Let be an alphabet.
A language *L* over is *recognized by FA*
if there exists a finite automaton
such that *L* is the language recognized by .

__THE PUNPING LEMMA.__ A natural question is

- are all languages over recognized by FA?
- and if no can we characterize those languages which are recognized by FA?

Indeed let
*L* = {*w*_{1}, *w*_{2},..., *w*_{n}} be such
a language. We can easily make FAs
_{1},
_{1}, ...
_{n} recognizing the languages
*L*_{1} = {*w*_{1}},
*L*_{2} = {*w*_{1}}, ...,
*L*_{n} = {*w*_{n}},
respectively.
Then by using
-transitions
we can construct a single FA recognizing

L = L_{1} L_{2} ^{ ... } L_{n}. |
(3) |

Therefore, if a language *L* is not recognized by FA
then it must contain an infinite number of words.
This leads us to the following remark.

- (
*i*) -
*s*_{i+1}= (*s*_{i},*x*_{i}) for every*i*= 1^{ ... }*n*- 1, - (
*ii*) -
*s*_{i}*s*_{j}for*i*,*j*= 1^{ ... }*n*- 1 and*i**j*, - (
*iii*) *s*_{1}=*s*_{n}.

Indeed, let *s*_{1} be the initial state,
*q* be the number of states of
and *p* the number of letters.
Since *L* is infinite,
there exists a word
*w* = *x*_{1}^{ ... }*x*_{}
in *L* with lenght
> *q*.
Recognizing *w* requires at least *q* + 1 transitions:

s_{2} = (s_{1}, x_{1}), s_{3} = (s_{3}, x_{3}),...s_{} = (s_{-1}, x_{-1}), s_{+1} = (s_{}, x_{}). |
(4) |

At least two of the visited states

- (
*i*) -
*m*=*u**v**w*, - (
*ii*) -
*v*, - (
*iii*) - for every positive integer
*k*we have*u**v*^{k}*w**L*.

__CONSTRUCTION OF LANGUAGES RECOGNIZED BY FA__ We would like now to characterize those languages which
are recognized by FA.
To address this question we give a series
of four propositions and one theorem.
Each of these four propositions provide a mechanism (or rule)
to build languages recognized by FA.
Theorem 3 states that these rules allow us to build
all possible languages recognized by FAs.

- Proposition 4 expresses the fact that languages consisting of a single word consisting itself of a single letter are recognized by FA. This statement is an obvious consequence of the previous Proposition 1 and is illustrated by Figure 12.
- Proposition 5 expresses the fact that the union of two languages recognized by FA is itself recognized by FA. This statement is also trivial and was illustrated by Figure 4.
- Proposition 6 expresses the fact that the concatenation (or product) of two languages recognized by FA is also recognized by FA. This statement is also not difficult to prove and we have already used this result implicitely with most examples.
- Proposition 7
expresses the fact that the
*star*of a language recognized by FA is also recognized by FA. The star (or*Kleene closure*) of a language is defined and illustrated below.

__NORMALIZED FINITE AUTOMATA__ A finite automaton
= (, *S*, *I*, *F*,)
is *normalized* if it satisfies to the following properties

- has only one initial state, say
*s*, - has only one final (= accepting) state, say
*f*, - no transition leads to the initial state
*s*, or more formally, for every*t**S*and every*x*{} we have*s*(*t*,*x*), - no transition leaves from the final state
*f*, or more formally, for every*x*{} we have (*f*,*x*) = .

__THE UNION OF TWO LANGUAGES RECOGNIZED BY FA__ is a language recognized by FA.
Proposition 5
formulates this statement with DFAs
and Figure 15
illustrates it with normalized FAs.

Then, the language
*L*_{1} *L*_{2} is recognized by the NFA

_{1+2} = (, S_{1} S_{2},{s_{1}, s_{2}}, F_{1} F_{2},) |
(5) |

where the transition function is defined as follows for every

(s, x) = |
(6) |

__THE PRODUCT OF TWO LANGUAGES RECOGNIZED BY FA__ is a language recognized by FA.
Proposition 6
formulates this statement with DFAs
and Figure 16
illustrates it with normalized FAs.

We denote by *L*_{1}*L*_{2} (or *L*_{1}.*L*_{2}) the language consisting of
all words of the form *w*_{1}*w*_{2} (concatenation of *w*_{1} and *w*_{2})
where *w*_{1} and *w*_{2} belong to *L*_{1} and *L*_{2} respectively.
This language is called the __PRODUCT LANGUAGE__ of *L*_{1} by *L*_{2}

Then, the language *L*_{1}*L*_{2} is recognized by the NFA

_{1.2} = (, S_{1} S_{2},{s_{1}}, F_{2},) |
(7) |

where the transition function is defined as follows for every

(s, x) = |
(8) |

__KLEENE CLOSURE OF A LANGUAGE.__ Let be an alphabet and let *w* be a word over .
Let *n* be a non-negative integer.
First we define the *n*-th power of *w*, denoted by *w*^{n}, as follows:

w^{n} = |
(9) |

Let

L^{n} = |
(10) |

Then we define the

L^{ * } = L^{n}. |
(11) |

Therefore, a word

- either
*w*is the empty word - or there exists a positive integer
*n*and a word*u*such that*w*=*u*^{n}.

- is the set of all words over .
- Let
*L*^{+}be the union of all*L*^{n}with*n*> 0. Then*L*^{+}=*L*.*L*^{ * }. - If
*L**M*then*L*^{ * }*M*^{ * }. - For every non-negative integer
*n*we ahve*L*^{ * n}=*L*^{ * }. -
*L*^{ * * }=*L*^{ * }. -
(
*L*^{ * }+*M*^{ * })^{ * }= (*L*^{ * }.*M*^{ * })^{ * }. -
(
*L*^{ * }+*M*^{ * })^{ * }= (*L*+*M*)^{ * }.

__THE KLEENE CLOSURE OF A LANGUAGE RECOGNIZED BY FA__ is a language recognized by FA.
Proposition 7
formulates this statement with DFAs
and Figure 18
illustrates it with normalized FAs.

Then *L*^{ * } is recognized by the NFA

^{ * } = (, S, s, F,) |
(12) |

where the transition function is defined as follows for every

(s, x) = |
(13) |

__KLEENE THEOREM.__ We denote by
*R*_{0}() the set of all
languages of the form {*x*} for
*x* {}.
Then for a positive integer *n* we define
*R*_{n}()
as the set of languages over consisting of

- the languages of
*R*_{n-1}(), - the languages of the form
*L*+*M*for*L*,*M**R*_{n-1}(), - the languages of the form
*L*.*M*for*L*,*M**R*_{n-1}(), - the languages of the form
*L*^{ * }for*L**R*_{n-1}().

This suggests the introduction of the notion
of a *regular expression*.

2004-12-02