Deterministic finite automaton: Difference between revisions

Revision as of 17:11, 10 November 2021

Revision as of 06:47, 18 November 2021

Line 95:

==Local automata==

A '''local automaton''' is a DFA, not necessarily complete, DFA 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>