Content deleted Content added
m clean up, typo(s) fixed: above mentioned → above-mentioned, a augmented → an augmented |
m Open access bot: doi updated in citation with #oabot. |
||
Line 124:
{{main|Induction of regular languages}}
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=
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}}</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>.
| |||