Content deleted Content added
Citation bot (talk | contribs) Alter: template type, title. Add: series, chapter, isbn, pages, date. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar |
|||
Line 117:
* the DFA with a minimum number of states for a particular regular language (Minimization Problem)
DFAs are equivalent in computing power to [[nondeterministic finite automata]] (NFAs). This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can do. Also, given an NFA, using the [[powerset construction]] one can build a DFA that recognizes the same language as the NFA, although the DFA could have exponentially larger number of states than the NFA.<ref name=Sak105>Sakarovitch (2009) p.105</ref><ref name=Law63>Lawson (2004) p.63</ref> However, even though NFAs are computationally equivalent to DFAs, the above mentioned problems are not necessarily solved efficiently also for NFAs. The non-universality problem for NFAs is [[PSPACE complete]] since there are small NFAs with shortest rejecting word in exponential size. A DFA is universal if and only if all states are final states, but this does not hold for NFAs. The Equality, Inclusion and Minimization Problems are also PSPACE complete since they require forming the complement of an NFA which results in an exponential blow up of size.<ref>https://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf {{Bare URL PDF|date=March 2022}}</ref>
On the other hand, finite-state automata are of strictly limited power in the languages they can recognize; many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. The classic example of a simply described language that no DFA can recognize is bracket or [[Dyck language]], i.e., the language that consists of properly paired brackets such as word "(()())". Intuitively, no DFA can recognize the Dyck language because DFAs are not capable of counting: a DFA-like automaton needs to have a state to represent any possible number of "currently open" parentheses, meaning it would need an unbounded number of states. Another simpler example is the language consisting of strings of the form ''a<sup>n</sup>b<sup>n</sup>'' for some finite but arbitrary number of ''a'''s, followed by an equal number of ''b'''s.<ref name=Law46>Lawson (2004) p.46</ref>
| |||