Editing Deterministic finite automaton (section)

==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.{{sfn|Lawson|2004|p=129}}{{sfn|Sakarovitch|2009|p=228}}

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.{{sfn|Lawson|2004|p=129}} The class of languages accepted by Myhill graphs is the class of local languages.{{sfn|Lawson|2004| p=128}}

===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 />