Content deleted Content added
→Notes: improving some citations |
Citation bot (talk | contribs) Add: publisher, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine |
||
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>{{Cite web |
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>
Line 125:
Given a set of ''positive'' words <math>S^+ \subset \Sigma^*</math> and a set of ''negative'' words <math>S^- \subset \Sigma^*</math> one can construct a DFA that accepts all words from <math>S^+</math> and rejects all words from <math>S^-</math>: this problem is called ''DFA identification'' (synthesis, learning).
While ''some'' DFA can be constructed in linear time, the problem of identifying a DFA with the minimal number of states is NP-complete.<ref name="Complexity of Automaton Identificat">{{cite journal|last1=Gold|first1=E. M.|author1-link=E. Mark Gold|title=Complexity of Automaton Identification from Given Data|journal=Information and Control|volume=37|issue=3|pages=302–320|year=1978|doi=10.1016/S0019-9958(78)90562-4|ref=Gold78|doi-access=}}</ref>
The first algorithm for minimal DFA identification has been proposed by Trakhtenbrot and Barzdin<ref>{{Cite book | url=https://books.google.com/books?id=h5XOBQAAQBAJ&pg=PP1 |title = Finite Automata: Behavior and Synthesis|isbn = 9781483297293|last1 = De Vries|first1 = A.|date = 28 June 2014| publisher=Elsevier }}</ref> and is called the ''TB-algorithm''.
However, the TB-algorithm assumes that all words from <math>\Sigma</math> up to a given length are contained in either <math>S^+ \cup S^-</math>.
Line 148:
'''Read-only right-moving Turing machines''' are a particular type of [[Turing machine]] that only moves right; these
are almost exactly equivalent to DFAs.<ref name=RORMTM>{{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker | title = Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| ___location = San Diego | year = 1994|
The definition based on a singly infinite tape is a 7-[[tuple]]
Line 231:
==References==
* {{cite book |last1=Hopcroft |first1=John E. |author-link1=John Hopcroft |last2=Motwani |first2=Rajeev |author-link2=Rajeev Motwani |last3=Ullman |first3=Jeffrey D. |author-link3=Jeffrey Ullman |title=[[Introduction to Automata Theory, Languages, and Computation]] |edition=2 |publication-place=Boston |url= |access-date=
* {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }}
* {{cite journal
| |||