2
$\begingroup$

I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular expressions. He does this by giving regular expressions, breaking them down into simpler regular expressions that represent the constituent pieces of the whole expression, creating a finite automata for each piece of the expression, and finally connecting them with the finite automata at the bottom that accepts the language described by the regular expression.

One of his examples is the sequence of finite automata in the picture attached, meant to illustrate how one might work through creating a finite automata that accepts the regular expression $(a\cup b)^* aba$.

With his definitions of union, concatenation, and star below.

Concatenation: $A+B=\{xy\mid x\in A\wedge y \in B\}$

Star: $A* = \{x_1x_2...x_k \mid k\geq 0 \wedge x_i \in A\}$

Union: $A\cup B = \{x\mid x\in A\vee x\in B\}$

At one point in the book he explains that two characters next to one another with no symbol between can imply concatenation so I am interpreting the "$aba$" piece as $a+b+a$.

I would think a finite automata that accepts $aba$ would have four states, with an "$a$" transition arrow between the first and second states, a "$b$" transition arrow between the second and third states, and an "$a$" transition arrow between the third state and the accept (fourth) state. The diagram instead is similar to what I imagined but adding a state with an empty string transition arrow between each state I described. See the 5th diagram, given for expression $aba $below Sequence of finite automata that accept components of regular expression <span class=$(a \cup b)^*aba$ illustrating how one might go about constructing a finite automaton that accepts the language described by that regular expression.">

These states with associated empty string transition arrows appear in both of the regular expression examples with concatenation he gives, so I must be misunderstanding something. There's a section in the book when he introduces nondeterministic finite automata in part of an effort to prove that regular languages are closed under the concatenation operation and mentions that "In general, an NFA may have arrows labeled with members of the alphabet or $\varepsilon$", and I figure the answer must have something to do with that, but I still don't understand why.

$\endgroup$
  • 2
    $\begingroup$ The $\varepsilon$ edges seem to be "glue" between two already defined NFAs. They are merely to make the construction easier (or harder?) to understand. In fact it's not hard to see how each such edge in the picture could be eliminated. $\endgroup$ – Solomonoff's Secret Nov 22 '18 at 2:44
  • $\begingroup$ It seems like you're implying that the finite automata I anticipated is equivalent to the finite automata suggested by the book, but I don't understand how/why. Earlier in the book, he suggests pretending you are the machine by tracing the path of the inputs. As I do that, I don't encounter any empty strings, since aba doesn't have ε, how can it be said that these machines accept the same languages? $\endgroup$ – PrehensileDreams Nov 22 '18 at 3:04
  • $\begingroup$ The author intends that when you visit a state, you should follow the $\varepsilon$ edges out of that state without consuming any more of the input - that is, the automaton is the same as if you eliminated those edges and identified the neighboring states (at least in the examples above). So o -a-> o -$\varepsilon$-> o -b-> o -$\varepsilon$-> o -a-> o is equivalent to o -a-> o -b-> o -a-> o. $\endgroup$ – Solomonoff's Secret Nov 22 '18 at 3:16
  • $\begingroup$ Welcome to this site. It is recommended that you'll read this article about using MathJax in questions. $\endgroup$ – Dean Gurvitz Nov 22 '18 at 7:20
1
$\begingroup$

An $\varepsilon$ transition (called the empty transition from here on out) from $A$ to $B$ means that if you end up in $A$ after a transition you can go to $B$ for free without consuming a character from the input.

When concatenating $a$ and $b$, $a$ may have multiple end states so it is easier to add an empty transition from every end state of $a$ to the start state of $b$.

You can make the rule so when you concatenate all outgoing transitions of the start state of $b$ is copied to every end state of $a$ and if the start state of $b$ is not an end state then the end states of $a$ are not end states of the concatenated NFA.

This is a much more complicated rule than: every end state of $a$ is no longer an end state and gets a new empty transition to the start state of $b$.

Adding the empty transitions does not change the language being accepted and you can do a minimization/optimization pass after constructing the NFA to eliminate the excess empty transitions.

This is actually a common practice in compilers, the early code generation is dumb and does the obvious, easy and non-optimal but correct thing. Then optimization passes look for patterns that can be simplified or optimized. This means that the pattern can be optimized everywhere even when it wasn't generated by the construct that commonly creates it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.