Computation - Patterns to Automaton

What If?

So, now we’ve seen a way to transform an automaton into a pattern. BUT! How do we go about doing it the other way around? How do we transform a pattern into its counterpart automaton?



It is very difficult to read off an automaton from a pattern. We therefore introduce an algorithm that works for all regular expression. This algorithm is recursive, and it builds on definition 4, making use of the recursive structure of patterns. It is very easy to build automata for the base cases. However, to build automata for the constructors of patterns alternative, concatenation, and star, we need to be a bit cleverer. Assume that we want to build an automaton for the regular expression a*b* based on already having automata for the patterns a* and b*. These are quite simple to construct:

and                    

Now all we need to do is stick the 2 automatons together. To do this we shall use ‘ε’ because it doesn’t consume any letters in a given word. So now we have:



And there you have it! The automaton that recognizes the pattern a*b*.

———————————————————————————————–

Definition 13: Let Σ be an alphabet not containing ε. An NFA with ε-transitions over Σ is an NFA over the alphabet Σ that may have transitions labeled with ε – like you saw above.

———————————————————————————————–

It is probably best to note, that if you are given an NFA with ε-transitions, then we are allowed to follow this edge without matching the next letter in a given word.

Another Algorithm

When you construct an NFA containing ε-transitions, it is not wise to keep them around. Here we introduce another algorithm that removes the ε-transitions from such an automaton. Consider the following automaton with ε-transitions:



From this, we now draw up new states, with new accepting states. Now, from looking at the above automaton, it is clear that state 1 is an unreachable state because we can only get to it using an ε-transition – remember, the ε’s are going to get removed. There, we have a blueprint of:



Now, look at the transitions labeled with ‘a’. It’s clear that we can go straight to state 2 from 0 with an a, and well as loop around on state 2 with an ‘a’. So now we have:



Now we look at the transitions labeled with a ‘b’. Here we can still loop round on state 2 with a ‘b’. So now we have:



Now all we have to do is remove the unreachable states. That is, remove states 1 and 3:



Automatons that Recognize certain Patterns

Now we are ready to look at how some certain patterns, like a* and ε can be transformed into an automaton! Firstly let’s start with the main ones:

• Ø – The empty set. The automaton to recognize this is:
  


• ε – The empty word. The automaton to recognize this is:
  


• x -  x Є Σ. The automaton for this is:
  

Now then, assume that we have the patterns p, p₁ and p₂. Then we can form the concatenation, alternative and Kleene star automatons.

• Concatenation: p₁p₂.
  


• Alternative: p₁|p₂.
  


• Kleene Star: p*.