Kleene star of an automaton
Let be an automaton. Define the Kleene star of as an automaton with -transitions (http://planetmath.org/AutomatonWithEpsilonTransitions) where
- 1.
(we either assume that is not a symbol in , or we take the disjoint union
)
- 2.
is a function from to given by:
- –
if , for any ,
- –
, for any , and
- –
otherwise.
- –
- 3.
Basically, we throw into all transitions in . In addition, we add to transitions taking to any initial states of , as well as transitions taking any final states of to . Visually, the state diagram of is obtained by adding a node to the state diagram of , and making both the start and the final node of . Furthermore, add edges from to the start nodes of , and edges from the final nodes of to , and let be the label for all of the newly added edges.
Proposition 1.
.
Proof.
Clearly . In addition, since , . This proves the case when the word is empty. Now, we move to the case when the word has non-zero length.
- •
.
Suppose is a word such that , then we claim that , where , is accepted by . This can be proved by induction
on :
- (a)
First, . Then
Since is accepted by , contains an accepting state , so that
Hence is accepted by .
- (b)
Next, suppose that given , the subword (induction step) is accepted by . This means that , so that
But contains as was shown in step 1 above. As a result, is accepted by .
This shows that .
- (a)
- •
.
Suppose now that is a word over accepted by . This means that, for some , , the word
is accepted by , where each is a word over with . We want to show that each is accepted by .
The main thing is to notice is that if and , where is a positive integer, then must contain a state in . Otherwise, , so that , and we must have .
Set and . Then . Furthermore, by assumption
. Therefore, must contain a state in . Thus, is accepted by . The fact that the remaining ’s are accepted by is proved inductively.
This shows that .
This completes the proof.∎