Deterministic finite automaton: Difference between revisions

Revision as of 02:53, 29 November 2024

Latest revision as of 06:30, 14 April 2025

(4 intermediate revisions by 4 users not shown)

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>| isbn = 978-1-7281-1519-1

}}</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 31 ⟶ 32:

==Formal definition==

A deterministic finite automaton {{mvar|M}} is a 5-[[n-tuple|tuple]], {{math|(''Q'', Σ, ''δ'', ''q''₀, ''F'')}}, consisting of

* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] {{mvar|Q}}

* a finite set of input symbols called the [[Alphabet (computer science)|alphabet]] {{math|Σ}}

* a transition [[function (mathematics)|function]] {{math|''δ'' : ''Q'' × Σ → ''Q''}}

* an initial (or [[Finite-state machine#Start state|start) state]] <math>q_0 \in Q</math>

* a set of [[Finite-stateaccepting machine#Accept .28or(or final.29 states|accept) states]] <math>F \subseteq Q</math>

Let {{math|1=''w'' = ''a''₁''a''₂...''a_n''}} be a string over the alphabet {{math|Σ}}. The automaton {{mvar|M}} accepts the string {{mvar|w}} if a sequence of states, {{math|''r''₀, ''r''₁, ..., ''r_n''}}, exists in {{mvar|Q}} with the following conditions:

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.

Line 261 ⟶ 263:

==References==

* {{Hopcroft and Ullman 1979|author-link=no|title-link=no}}{{sfn whitelist|CITEREFHopcroftUllman1979}}

* {{Hopcroft, Motwani, and Ullman 2006}}{{sfn whitelist|CITEREFHopcroftMotwaniUllman2006}}

* {{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

Line 298 ⟶ 300:

{{DEFAULTSORT:Deterministic Finite-State Machine}}

[[Category:Finite-state automatamachines]]