Talk:Deterministic finite automaton: Difference between revisions

Revision as of 14:17, 9 October 2019

Revision as of 22:12, 4 September 2020

Line 112:

The description of classifiers claims that a classifier has "has more than two terminal states", which seems to imply that a DFA cannot have more than two terminal states. Should this be "more than two ''classes'' of terminal states"? A DFA can obviously have three terminal states, but just two classes (accept and reject). This is not clear from the current wording on classifiers. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/131.174.142.107|131.174.142.107]] ([[User talk:131.174.142.107#top|talk]]) 14:16, 9 October 2019 (UTC)</small> <!--Autosigned by SineBot-->

== Definition of local automaton ==

[[Deterministic_finite_automaton#Local_automata]] says "A local automaton is a DFA for which all edges with the same label lead to a single vertex." I suggest adding "not necessarily complete" before "DFA". If we require the DFA to be complete as specified in [[Deterministic_finite_automaton#Formal_definition]], then it is not true that local automata can accept all local languages.

For example, consider the local language <math>A</math> consisting of all strings on <math>{a, b, c}</math> that do not contain <math>ab</math>. If <math>M</math> is a complete DFA in which all edges with the same label lead to a single vertex, then <math>A</math> is not the language accepted by <math>M</math>. Proof: Note that <math>ccc \in A</math> but <math>abc \notin A</math>. Let <math>q</math> be the state of <math>M</math> such that all edges with label <math>c</math> lead to <math>q</math>. Then <math>M</math> terminates at <math>q</math> with input <math>abc</math> or <math>ccc</math>, so it either accepts both or rejects both. Therefore <math>A</math> is not the language accepted by <math>M</math>.

I have not checked the references in this section to see how they define DFA. "Local languages and the Berry-Sethi algorithm" (at https://www.irif.fr/~jep/PDF/BerrySethi.pdf) has a proof that every local language is accepted by a local automaton (Proposition 2.1). Immediately before that, its definition of local automaton includes "not necessarily complete". [[Special:Contributions/2600:1700:6EC0:35C0:D5F2:3A1:B655:C5F7|2600:1700:6EC0:35C0:D5F2:3A1:B655:C5F7]] ([[User talk:2600:1700:6EC0:35C0:D5F2:3A1:B655:C5F7|talk]]) 22:12, 4 September 2020 (UTC)