Content deleted Content added
DuncanHill (talk | contribs) Template:Sfn whitelist fixes ref errors caused by "clever" citations |
Citation bot (talk | contribs) Add: publisher, issue, isbn, authors 1-3. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Mathbot/Possible_redirects | #UCB_webform_linked 100/972 |
||
Line 25:
| publisher = IEEE / ACM
| title = Proceedings of the 27th International Conference on Program Comprehension, ICPC 2019, Montreal, QC, Canada, May 25-31, 2019
| year = 2019
}}</ref>
DFAs have been generalized to ''[[nondeterministic finite automata]] (NFA)'' which may have several arrows of the same label starting from a state. Using the [[powerset construction]] method, every NFA can be translated to a DFA that recognizes the same language. DFAs, and NFAs as well, recognize exactly the set of [[regular language]]s.{{sfn|Hopcroft|Motwani|Ullman|2006}}
Line 116 ⟶ 117:
| title = Grammars and languages
| volume = 76
| year = 1969| issue = 4
}}</ref> *Homomorphism<ref name=rose/><ref name=spanier/>
}}
Line 163 ⟶ 165:
Gold's algorithm assumes that <math>S^+</math> and <math>S^-</math> contain a ''[[Characteristic Samples|characteristic set]]'' of the regular language; otherwise, the constructed DFA will be inconsistent either with <math>S^+</math> or <math>S^-</math>.
Other notable DFA identification algorithms include the RPNI algorithm,<ref>{{Cite book | doi=10.1142/9789812797902_0004| chapter=Inferring Regular Languages in Polynomial Updated Time| title=Pattern Recognition and Image Analysis| volume=1| pages=49–61| series=Series in Machine Perception and Artificial Intelligence| year=1992| last1=Oncina| first1=J.| last2=García| first2=P.| isbn=978-981-02-0881-3}}</ref> the Blue-Fringe evidence-driven state-merging algorithm,<ref>{{Cite book |doi = 10.1007/BFb0054059|chapter = Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm|title = Grammatical Inference|volume = 1433|pages = 1–12|series = Lecture Notes in Computer Science|year = 1998|last1 = Lang|first1 = Kevin J.|last2 = Pearlmutter|first2 = Barak A.|last3 = Price|first3 = Rodney A.|isbn = 978-3-540-64776-8|url = http://eprints.maynoothuniversity.ie/10250/1/BP-Results-1998.pdf}}</ref>
and Windowed-EDSM.<ref>{{Cite book | url=https://dl.acm.org/doi/abs/10.5555/645519.655966 | title=Beyond EDSM {{pipe}} Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and Applications| date=23 September 2002| pages=37–48| isbn=9783540442394| last1=Adriaans| first1=Pieter| last2=Fernau| first2=Henning| last3=Zaanen| first3=Menno van| publisher=Springer}}</ref>
Another research direction is the application of [[evolutionary algorithm]]s: the smart state labeling evolutionary algorithm<ref>{{Cite journal |doi = 10.1109/TPAMI.2005.143|pmid = 16013754|title = Learning deterministic finite automata with a smart state labeling evolutionary algorithm|journal = IEEE Transactions on Pattern Analysis and Machine Intelligence|volume = 27|issue = 7|pages = 1063–1074|year = 2005|last1 = Lucas|first1 = S.M.|last2 = Reynolds|first2 = T.J.|s2cid = 14062047}}</ref> allowed to solve a modified DFA identification problem in which the training data (sets <math>S^+</math> and <math>S^-</math>) is ''noisy'' in the sense that some words are attributed to wrong classes.
| |||