Proof:
We do this again by induction on the syntax of regular expressions:
which will reject everything (it has got no final states) and hence
![]() |
![]() |
|
![]() |
This automaton accepts the empty word but rejects everything else, hence:
![]() |
![]() |
|
![]() |
This automaton only accepts the word x, hence:
![]() |
![]() |
|
![]() |
We merge the diagrams for
and
into one:
I.e. given
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
Just thinking of the game with markers you should be able to convince yourself that
Moreover to show that
![]() |
![]() |
|
![]() |
![]() |
Now putting everything together:
![]() |
![]() |
|
![]() |
||
![]() |
We want to put
the two automata and
in series. We do this by
connecting the final states of
with the initial states
of
in a way explained below.
In this diagram I only depicted one initial and one final state of each of the automata although they may be several of them.
Here is how we construct from
and
:
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
|
![]() |
||
![]() |
![]() |
I hope that you are able to convince yourself that
![]() |
![]() |
![]() |
|
![]() |
We construct from
by merging initial and final
states of
in a way similar to the previous construction and
we add a new state
which is initial and final.
Given
![]() |
![]() |
![]() |
![]() |
|
![]() |
We claim that
![]() |
![]() |
|
![]() |
||
![]() |
||
![]() |
I.e. using brackets does not change anything.
As an example we construct
. First we
construct
:
Now we have to apply the -construction and we obtain:
is just the same and we get
and now we have to serialize the two automata and we get:
Now, you may observe that this automaton, though correct, is unnecessary complicated, since we could have just used
However, we shall not be concerned with minimality at the moment.