9
$\begingroup$

DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study all the three form of representation of finite automata? There can some explanation on what NFA can do which DFA cannot , that is NFA might help us in designing uncertainties. For example in designing a game (chess), we have many options to move a particular piece from a particular location which can be easily represented using NFA. But what is the use of epsilon NFA when the same can done using NFA or DFA?

$\endgroup$
  • 2
    $\begingroup$ There are more than three. These are just the ones typically found in textbooks. Epsilon transitions are useful for proving theorems, but I'm not sure I've seen them used in models for their own sake. $\endgroup$ – wvxvw Feb 27 '16 at 19:58
  • 3
    $\begingroup$ @wvxvw, the algorithm for translating a regular expression into a NFA uses $\epsilon$ transitions in a very natural way. They are not "only for proofs", they are quite natural in a non-deterministic setting. $\endgroup$ – vonbrand Feb 27 '16 at 20:08
13
$\begingroup$

Add regular grammars for a fourth. There are others...

Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a crucial idea for more elaborate models). To prove DFA and NFA accept the same set of languages is also exploring a very important phenomenon in a simple, understandable setting.

Regular expressions (and also regular grammars) are completely different formalisms, that happen to describe the same set of languages. Again, the proof of this fact explores important cross-relations, and are an example that formalisms might look very diffent, be based on radically dissimilar concepts, but describe the same languages. Again, in a rather simple setting.

For "real world" use, you can start with a regular expression and get a minimal DFA for high-performance searching. Digital circuits are essentially DFAs, understanding them is central in computer engineering. Last but not least, often systems can be modelled as "being in a state" and "moving to another one" on external stimuli, even if the system is very far from a real DFA viewing it this way might help understanding it.

Added later: As noted by Raphael, it may be more efficient to interpret an NFA directly for searching, because creating a DFA can be expensive, and an NFA may be much smaller.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "There are others" -- dozens.... $\endgroup$ – Raphael Feb 29 '16 at 20:13
  • 1
    $\begingroup$ You may want to mention that NFA can be useful (if DFA are the only alternatice) because they can be a lot smaller, but using one to check if a word is accepted is not too much more expensive. $\endgroup$ – Raphael Feb 29 '16 at 20:15
5
$\begingroup$

there are a wide variety of reasons to study the different forms/ correspondences of DFAs vs NFAs. here are a few selected highlights some from advanced complexity theory.

  • NFAs are a interesting model for "parallel computation". one can regard the advancement of states through the NFA as a parallel version of DFA computation. so DFA vs NFA computations reflect some of the distinction of sequential vs parallel computation. by comparing both contexts it also helps to study the inherent algorithmic complexity of problems.

  • NFAs are often used in regular expression matching systems (quite ubiquitous across languages esp modern ones spawned in the unix era), which typically allow descriptions of regular expressions that are converted to NFAs, and then possibly converted to DFAs to aid with more efficient searching.

  • there are quite a few open problems that remain in the areas and they are often studied based on the DFA/ NFA correspondence. see eg are there any open problems left on DFAs (cstheory stackexchange). somewhat amazingly, some of them are tied up with very deep areas of CS including the P vs NP problem ie intersection nonemptiness of DFAs. also another open area is eg computing the minimal NFA for a DFA.

  • also for some related insight see this semifamous/ highvoted question on cstheory.se: What is the enlightenment I'm supposed to attain after studying finite automata?

  • there are very diverse applications of DFAs vs NFAs and the correspondence between the two is often exploited in them. string pattern matching is mentioned above, but DFA/NFA constructions are used often in (automated) speech recognition. see eg this highly cited paper: Weighted Finite-State Transducers in Speech Recognition / Mohri, Pereira, Riley

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

DFAs has a easier implementation than NFA since their next state is determined by a function and NFAs help a user to easily express what they want as an output, because the NFA can choose between multiple paths. and epsilon-NFA is an extension of NFA where transitions can be done without taking any input symbols.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ summarizing: NFAs convey the idea of non-determinism, which is a very profound idea (its "inventors", Michael O. Rabin and Dana S. Scott, won the Turing award for these ideas) $\endgroup$ – Ran G. Mar 12 '16 at 15:45
1
$\begingroup$

There is a nasty thing about the number of states of DFAs. It explodes, sometimes.

In short, if the number of states is simply too high (still finite but we live in a physical world.), then you have to increase the level of abstraction to cope with the complexity in expense of some slowdown. The other models, like NFAs and AFAs, are to provide more succinct ways to represent regular languages.

| cite | improve this answer | |
$\endgroup$

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