##### Finite Automata

##
Kleene's Theorem --- Part 1

### Subjects to be Learned

- Union of FAs
- Concatenation of FAs
- Kleene Star of FAs
- Acceptance of regular languages by FAs

### Contents

In this unit we are going to learn Kleene's theorem. It states that any regular language is accepted by an FA
and conversely that any language accepted by an FA is regular.

**Theorem 1 (Part 1 of Kleene's theorem):**
Any regular language is accepted by a finite automaton.

**Proof:** This is going to be proven by (general) induction following
**the recursive definition of regular language**.

**Basis Step:**
As shown below the languages
,
{} and
{ a } for any symbol a in
are accepted by an FA.

**Inductive Step:** We are going to show that for any languages L_{1} and L_{2}
if they are accepted by FAs, then L_{1} L_{2} ,
L_{1}L_{2} and L_{1}^{*} are accepted by FAs.
Since any regular language is obtained from
{} and
{ a } for any symbol a in
by using union, concatenation and Kleene star operations,
that together with the Basis Step would prove the theorem.

Suppose that L_{1} and L_{2} are accepted by FAs M_{1} = < Q_{1} , ,
q_{1,0} , _{1} , A_{1} >
and M_{2} = < Q_{2} , ,
q_{2,0} , _{2} , A_{2} > , respectively.
We assume that Q_{1} Q_{2} = without loss of generality since states can be renamed if necessary.

Then L_{1} L_{2} ,
L_{1}L_{2} and L_{1}^{*} are accepted by the FAs
M_{u} = < Q_{u} , ,
q_{u,0} , _{u} , A_{u} >
, M_{c} = < Q_{c} , ,
q_{c,0} , _{c} , A_{c} >
and M_{k} = < Q_{2} , ,
q_{k,0} , _{k} , A_{k} > , respectively, which are given below.

**M**_{u} = < Q_{u} , ,
q_{u,0} , _{u} , A_{u} > :

Q_{u} = Q_{1} Q_{2}
{ q_{u,0} } , where q_{u,0} is a state which is neither in Q_{1} nor in Q_{2} .

_{u} = _{1}
_{2}
{ (q_{u,0}, , { q_{1,0} , q_{2,0} } ) } ,
that is _{u}(q_{u,0}, ) =
{ q_{1,0} ,
q_{2,0} } . Note that _{u}(q_{u,0}, a ) =
for all a in .

A_{u} = A_{1} A_{2}

**M**_{c} = < Q_{c} , ,
q_{c,0} , _{c} , A_{c} > :

Q_{c} = Q_{1} Q_{2}

q_{c,0} = q_{1,0}

_{c} = _{1}
_{2}
{ (q, , { q_{2,0} } ) | q A_{1} }

A_{c} = A_{2}

**M**_{k} = < Q_{k} , ,
q_{k,0} , _{k} , A_{k} > :

Q_{k} = Q_{1}
{ q_{k,0} } , where q_{k,0} is a state which is not in Q_{1} .

_{k} = _{1}
{ (q_{k,0}, , { q_{1,0} } ) }
{ (q, , { q_{k,0} } ) | q A_{1} }

A_{k} = { q_{k,0} }

These NFA-s are illustrated below.

It can be proven, though we omit proofs, that these NFA-s , M_{u}, M_{c}
and **M**_{k} , in fact accept **L**_{1} L_{2} ,
L_{1}L_{2} and **L**_{1}^{*}, respectively.

**
End of Proof
**

**
Examples of M**_{u} , M_{c}
and **M**_{k}:

**Example 1:**
An NFA- that accepts the language represented by the regular expression
(aa + b)^{*} can be constructed as follows using the operations given above.

**Example 2:**
An NFA- that accepts the language represented by the regular expression
((a + b)a^{*})^{*} can be constructed as follows using the operations given above.

### Test Your Understanding of Kleene's Theorem Part 1

Indicate which of the following statements are correct and which are not.

Click True or Fals , then Submit.

**
Next -- Kleene's Theorem --- Part 2 **

**
Back to Study Schedule **

**
Back to Table of Contents **