NFA->DFA - Why use epsilon transitions?

[Alexander Morou]

I have a question about epsilon transitions in standard NFA
implementations: What exactly are they for?

I've never really understood their purpose, other than to confuse
people trying to understand FSA and regular languages (with respect
to language scanner generation).

This is a standard overview of NFA, DFA, and translation from one
to the other (by I guess Donald R. Biggar, circa '04; using the
small grammar "ab*(bc)*"):
http://www3.sympatico.ca/dbiggar/FA.home.html

Since I'm useless with formal theory, I figured I'd follow his
pattern and describe mine using a visual representation:
http://alexandermorou.com/images/nfa_to_dfa.jpg

Basically all I needed was a small lookup that contained the
transition requirement (ie. the character range) and the state
set that was transitioned to by that requirement. When
rebuilding the expression in DFA form, if a DFA node for the
NFA set and requirement doesn't exist, one is created; otherwise,
the node is retrieved from cache. The actual transitions
for each DFA node is the union of the transitions used to
create that node. This can potentially create new overlaps
so the node is created and inserted into cache before its individual
transitions are evaluated.

The code for DFA conversion is surprisingly small, and once I understood
the basics, the rest was easy. Is there something I missed in this
implementation, or is that really all there is?

I'm wondering if the entire reason I didn't need epsilon transitions
was the method I used to build the NFA structure in the first place.
I used the Kleene operators, and kept tabs on the last required element
relative to the current element, and merged the transitions backwards
through the state edges for every discrete node in the expression,
setting and clearing the edge status of nodes based upon whether the
next node element in the expression was required (ie. ac?d?e?b would
have the transition set of 'c','d','e' and 'b' after 'a' from the start.)

Naturally that doesn't get into state reduction, which was easy
once the other was done, but that's another matter.
http://compilers.iecc.com/comparch/article/09-02-146
Chris F Clark was nice enough to explain the difference between
throwing too much away for simple recognition, and just enough
for a transducer.

Thanks in advance,

[Stephen Horne]

On Tue, 7 Apr 2009 12:36:47 -0500, Alexander Morou
<alexand...@gmail.com> wrote:

>I have a question about epsilon transitions in standard NFA
>implementations: What exactly are they for?

One reason is that many different automata compositions can be
implemented very simply using epsilon transitions. You then use a
single simple epsilon-elimination and nondeterminism-reducing
algorithm rather than needing to build that complexity into every
composition algorithm.

For example...

Concatenation - draw an epsilon transition from each end-state in the
first machine to each begin-state in the second machine.

Repeat one-or-more - draw an epsilon transition from each end-state to
each begin-state.

Optional - draw an epsilon transition from each begin-state to each
end-state.

Ragel is a program which allows lexical analysis code to be generated,
and which composes FSMs in this kind of way. The manual is pretty good
at explaining how each of the composition operators works.

http://www.complang.org/ragel/

If you don't do FSM composition - e.g. if you derive the whole FSM
model in one step - I would guess that epsilon transitions aren't
useful (though I am far from expert, and may well be wrong). However,
if you use this approach, I'm not sure why you would be dealing with
nondeterministic automata anyway.

[alexand...@gmail.com]

> If you don't do FSM composition - e.g. if you derive the whole FSM
> model in one step - I would guess that epsilon transitions aren't
> useful (though I am far from expert, and may well be wrong). However,
> if you use this approach, I'm not sure why you would be dealing with
> nondeterministic automata anyway.

Actually I still need the non-determinism in NFA for the system
initially. This is due to the nature of the way it's built, I
can't guarantee what's 'next' so prematurely making DFA states
based upon only part of the equation (as it's being built), would
lead to an incorrect DFA result. So the NFA step is still necessary.
After your simple explanation and reading up more on epsilon
transitions, all I've really done is the same thing, without the extra
epsilon steps. Since the goal in this case is clear and not intended
for multiple types of input, I can get away with a simpler non-eps.
version.

Though ironically I've started using a similar system in another area
of the project, which uses the same code (adjusted for type
differences)
to create the same kind of graphs. I'm hoping to make a simple
visualizer for DFA/NFA for the visual layout experience. Though due
to the language I'm using, I still don't think that I would've needed
epsilon transitions, but rather an abstraction layer for the system
to operate upon in which common functional aspects are represented in
a uniform manner (generic typing models are nice).

[Torben Ægidius Mogensen]

Alexander Morou <alexand...@gmail.com> writes:

> I have a question about epsilon transitions in standard NFA
> implementations: What exactly are they for?
>
> I've never really understood their purpose, other than to confuse
> people trying to understand FSA and regular languages (with respect
> to language scanner generation).

As Stephen Horne mentioned, the most compelling reason is to allow
NFAs for regular expressions to be built compositionally from regular
expressions in an easy way. There are methods for building
epsilon-free NFAs compositionally from epsilon-free regular
expressions, but these are much more complicated.

Also, with epsilon transitions, the size of an NFA for a regexp of
size N is O(N) states and O(N) transitions, but without epsilon
transitions, the maximal size increases to O(N) states and O(N^2)
transitions. Granted, that is not important if you intend to convert
to a DFA afterwards, as this has O(2^N) states and transitions.

Torben

[Vimal]

I would like to add the following point to Stephen Horne's list.

2009/4/7 Alexander Morou <alexand...@gmail.com>:

>
> I'm wondering if the entire reason I didn't need epsilon transitions
> was the method I used to build the NFA structure in the first place.

Actually, conversion from a regular expression to a NFA is IMHO much
easier, as is outlined in many textbooks (1). The size of a NFA is
usually much smaller (and for some cases, exponentially smaller) than
a DFA. The NFA which you get by following the method (1) is called the
Thompson NFA. On a computer, it might sometimes be more effective to
maintain a subset of states as a bit-vector as opposed to maintaining
a single state on a DFA with possibly exponential number of states.
This page outlines some aspects:

http://swtch.com/~rsc/regexp/regexp1.html

--
Vimal