Kleene star of an automaton
(we either assume that is not a symbol in , or we take the disjoint union)
is a function from to given by:
if , for any ,
, for any , and
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.
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 :
First, . Then
Since is accepted by , contains an accepting state , so that
Hence is accepted by .
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 .
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. ∎
|Title||Kleene star of an automaton|
|Date of creation||2013-03-22 18:04:06|
|Last modified on||2013-03-22 18:04:06|
|Last modified by||CWoo (3771)|