patternModerate
Why should we study all the three forms of representation of finite automata?
Viewed 0 times
threewhythefinitestudyallautomatashouldrepresentationforms
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#53693, answer score: 13
Revisions (0)
No revisions yet.