Content deleted Content added
→See also: clean up links |
improve section organization |
||
Line 34:
For more comprehensive introduction of the formal definition see [[automata theory]].
==Complete and incomplete==▼
According to the above definition, deterministic finite automata are always ''complete'': they define from each state a transition for each input symbol.▼
While this is the most common definition, some authors use the term deterministic finite automaton for a slightly different notion: an automaton that defines ''at most'' one transition for each state and each input symbol; the transition function is allowed to be [[partial function|partial]].<ref name="Mogensen">{{cite book | last=Mogensen | first=Torben Ægidius | title=Introduction to Compiler Design | chapter=Lexical Analysis | series=Undergraduate Topics in Computer Science | publisher=Springer | ___location=London | year=2011 | doi=10.1007/978-0-85729-829-4_1 | page=12| isbn=978-0-85729-828-7 }}</ref> When no transition is defined, such an automaton halts.▼
==Example==
Line 61 ⟶ 56:
The language recognized by {{mvar|M}} is the [[regular language]] given by the [[regular expression]] <code>(1*) (0 (1*) 0 (1*))*</code>, where <code>*</code> is the [[Kleene star]], e.g., <code>1*</code> denotes any number (possibly zero) of consecutive ones.
==Variations==
▲===Complete and incomplete===
▲According to the above definition, deterministic finite automata are always ''complete'': they define from each state a transition for each input symbol.
▲While this is the most common definition, some authors use the term deterministic finite automaton for a slightly different notion: an automaton that defines ''at most'' one transition for each state and each input symbol; the transition function is allowed to be [[partial function|partial]].<ref name="Mogensen">{{cite book | last=Mogensen | first=Torben Ægidius | title=Introduction to Compiler Design | chapter=Lexical Analysis | series=Undergraduate Topics in Computer Science | publisher=Springer | ___location=London | year=2011 | doi=10.1007/978-0-85729-829-4_1 | page=12| isbn=978-0-85729-828-7 }}</ref> When no transition is defined, such an automaton halts.
===Local automata===▼
A '''local automaton''' is a DFA, not necessarily complete, for which all edges with the same label lead to a single vertex. Local automata accept the class of [[Local language (formal language)|local languages]], those for which membership of a word in the language is determined by a "sliding window" of length two on the word.<ref name=Law129>Lawson (2004) p.129</ref><ref name=Sak228>Sakarovitch (2009) p.228</ref>▼
A '''Myhill graph''' over an alphabet ''A'' is a [[directed graph]] with [[Vertex (graph theory)|vertex set]] ''A'' and subsets of vertices labelled "start" and "finish". The language accepted by a Myhill graph is the set of directed paths from a start vertex to a finish vertex: the graph thus acts as an automaton.<ref name=Law129/> The class of languages accepted by Myhill graphs is the class of local languages.<ref name=Law128>Lawson (2004) p.128</ref>▼
===Randomness===
When the start state and accept states are ignored, a DFA of {{mvar|n}} states and an alphabet of size {{mvar|k}} can be seen as a [[Directed graph|digraph]] of {{mvar|n}} vertices in which all vertices have {{mvar|k}} out-arcs labeled {{math|1, …, ''k''}} (a {{mvar|k}}-out digraph). It is known that when {{math|''k'' ≥ 2}} is a fixed integer, with high probability, the largest [[strongly connected component]] (SCC) in such a {{mvar|k}}-out digraph chosen uniformly at random is of linear size and it can be reached by all vertices.<ref name=Grusho>{{cite journal|last1=Grusho|first1=A. A.|title=Limit distributions of certain characteristics of random automaton graphs|journal=Mathematical Notes of the Academy of Sciences of the USSR|date=1973|volume=4|pages=633–637|doi=10.1007/BF01095785|s2cid=121723743|ref=Grusho1973}}</ref> It has also been proven that if {{mvar|k}} is allowed to increase as {{mvar|n}} increases, then the whole digraph has a phase transition for strong connectivity similar to [[Erdős–Rényi model]] for connectivity.<ref name=Cai>{{cite journal |last1=Cai |first1=Xing Shi |last2=Devroye |first2=Luc |title=The graph structure of a deterministic automaton chosen at random |journal=Random Structures & Algorithms |date=October 2017 |volume=51 |issue=3 |pages=428–458 |doi=10.1002/rsa.20707|arxiv=1504.06238 |s2cid=13013344 }}</ref>▼
In a random DFA, the maximum number of vertices reachable from one vertex is very close to the number of vertices in the largest [[strongly connected component|SCC]] with high probability.<ref name=Grusho /><ref>{{cite conference |last1=Carayol |first1=Arnaud |last2=Nicaud |first2=Cyril |date=February 2012 |title=Distribution of the number of accessible states in a random deterministic automaton |volume=14 |pages=194–205 |conference=STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) |___location=Paris, France |url=https://hal.archives-ouvertes.fr/hal-00678213}}</ref> This is also true for the largest [[Glossary of graph theory#Subgraphs|induced sub-digraph]] of minimum in-degree one, which can be seen as a directed version of [[Degeneracy (graph theory)#k-Cores|{{math|1}}-core]].<ref name=Cai />▼
==Closure properties==
Line 93 ⟶ 105:
Repeated function composition forms a [[monoid]]. For the transition functions, this monoid is known as the [[transition monoid]], or sometimes the ''transformation semigroup''. The construction can also be reversed: given a <math>\widehat\delta</math>, one can reconstruct a <math>\delta</math>, and so the two descriptions are equivalent.
▲==Local automata==
▲A '''local automaton''' is a DFA, not necessarily complete, for which all edges with the same label lead to a single vertex. Local automata accept the class of [[Local language (formal language)|local languages]], those for which membership of a word in the language is determined by a "sliding window" of length two on the word.<ref name=Law129>Lawson (2004) p.129</ref><ref name=Sak228>Sakarovitch (2009) p.228</ref>
▲A '''Myhill graph''' over an alphabet ''A'' is a [[directed graph]] with [[Vertex (graph theory)|vertex set]] ''A'' and subsets of vertices labelled "start" and "finish". The language accepted by a Myhill graph is the set of directed paths from a start vertex to a finish vertex: the graph thus acts as an automaton.<ref name=Law129/> The class of languages accepted by Myhill graphs is the class of local languages.<ref name=Law128>Lawson (2004) p.128</ref>
▲When the start state and accept states are ignored, a DFA of {{mvar|n}} states and an alphabet of size {{mvar|k}} can be seen as a [[Directed graph|digraph]] of {{mvar|n}} vertices in which all vertices have {{mvar|k}} out-arcs labeled {{math|1, …, ''k''}} (a {{mvar|k}}-out digraph). It is known that when {{math|''k'' ≥ 2}} is a fixed integer, with high probability, the largest [[strongly connected component]] (SCC) in such a {{mvar|k}}-out digraph chosen uniformly at random is of linear size and it can be reached by all vertices.<ref name=Grusho>{{cite journal|last1=Grusho|first1=A. A.|title=Limit distributions of certain characteristics of random automaton graphs|journal=Mathematical Notes of the Academy of Sciences of the USSR|date=1973|volume=4|pages=633–637|doi=10.1007/BF01095785|s2cid=121723743|ref=Grusho1973}}</ref> It has also been proven that if {{mvar|k}} is allowed to increase as {{mvar|n}} increases, then the whole digraph has a phase transition for strong connectivity similar to [[Erdős–Rényi model]] for connectivity.<ref name=Cai>{{cite journal |last1=Cai |first1=Xing Shi |last2=Devroye |first2=Luc |title=The graph structure of a deterministic automaton chosen at random |journal=Random Structures & Algorithms |date=October 2017 |volume=51 |issue=3 |pages=428–458 |doi=10.1002/rsa.20707|arxiv=1504.06238 |s2cid=13013344 }}</ref>
▲In a random DFA, the maximum number of vertices reachable from one vertex is very close to the number of vertices in the largest [[strongly connected component|SCC]] with high probability.<ref name=Grusho /><ref>{{cite conference |last1=Carayol |first1=Arnaud |last2=Nicaud |first2=Cyril |date=February 2012 |title=Distribution of the number of accessible states in a random deterministic automaton |volume=14 |pages=194–205 |conference=STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) |___location=Paris, France |url=https://hal.archives-ouvertes.fr/hal-00678213}}</ref> This is also true for the largest [[Glossary of graph theory#Subgraphs|induced sub-digraph]] of minimum in-degree one, which can be seen as a directed version of [[Degeneracy (graph theory)#k-Cores|{{math|1}}-core]].<ref name=Cai />
==Advantages and disadvantages==
| |||