CODEWITHSUNDEEP
regexfinite-automata
Ant
Ant

Reputation: 37

Do not understand empty string in finite automata from regular expression

I am reading my textbook ("Introduction to the theory of computation" by Michael Sipser) and there is a part that is trying to convert the regular expression (ab U b)* into a non-deterministic finite automata. The book is telling me to break the expression apart and write a NFA for each piece. When it reaches ab it shows:

  1. An a to go from the first state to the second
  2. An empty string to go from the second state to the third
  3. A b to go from the third state to the final accepting state.

I am really confused trying to understand the second step. What's the purpose of the empty string. Would it be incorrect if it wasn't there?

Upvotes: 0

Views: 1017

Answers (1)

Fernando Aires
Fernando Aires

Reputation: 531

You're probably making reference to example 1.56, right? First of all, remember he is describing a process - think of it as an algorithm, that will be executed always in the same matter. What he's saying is that, if you have a regexp concatenation as P.Q, no matter what P and Q are, you can join their AFNs by connecting the ending states of P with an empty string to the starting state of Q.

So, in his example, he's creating an AFN to represent a.b. AFNs to represent a and b isolated are trivial, as:

->o-a->O

->o-b->O

So, in order to join both, you just follow the algorithm, putting an empty string connection from the final state of the first AFN to the starting state of the second algorithm, as:

->o-a->o-E->o-b->O

In this particular case, since it's very easy to create a a.b AFD, we look at it and perceive this empty string is not necessary. But the process works with every single concatenation - and, in fact, being self evident that this is equivalent of a trivially correct AFD just reinforces his statement: the process works.

Hope that helps.

Upvotes: 3

Related Questions