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.