Deterministic finite automaton: Difference between revisions

Revision as of 02:36, 29 November 2024

Revision as of 02:41, 29 November 2024

Line 78:

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

===Randomness===