Content deleted Content added
→Classifiers: new section |
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{WPCS}}, {{Maths rating}}. Remove 3 deprecated parameters: field, historical, vital. Tag: |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=Start|
{{WikiProject Computer science|importance=high}}
{{WikiProject Mathematics|importance=mid}}
}}
==Technical flag==
Line 59 ⟶ 55:
::I just added a new section to mention the difference. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 09:47, 11 November 2015 (UTC)
::It should be made clear that if a path is missing, the automaton halts ''and rejects the string''. [[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:26, 4 September 2020 (UTC)
== Possible error in example ==
Line 90 ⟶ 88:
* '''Support''' per nom. —''[[User:Ruud Koot|Ruud]]'' 20:37, 25 November 2011 (UTC)
:''The above discussion is preserved as an archive of a [[WP:RM|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:RM bottom -->
== DFA cannot recognize ''a<sup>n</sup>b<sup>n</sup>''? ==
Line 111 ⟶ 109:
== Classifiers ==
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">— 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)
:{{done}} I believe you are right. Although every DFA can be made complete by adding an "error" state, completing a local DFA will destroy locality. Also, your proof looks convincing. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 17:10, 5 September 2020 (UTC)
== Recognizing valid email addresses ==
The lead section mentions recognizing syntactically valid [[email address]]es as an application for deterministic finite automata. I am not sure if this is supposed to be an in-joke: the syntax and grammar of email addresses at least as defined by the original [[RFC 822]] is quite complex, and using DFAs (at least in the form of regular expressions) is kind of seen as an anti-pattern, at least as far as I understand it. See e.g. the discussion at [[Talk:Email address#Complexity of email addresses]] here on Wikipedia and the top answer to the question "[https://stackoverflow.com/questions/201323/how-to-validate-an-email-address-using-a-regular-expression/63841473#63841473 How to validate an email address using a regular expression?]" on [[Stack Overflow]]. – [[User:Tea2min|Tea2min]] ([[User talk:Tea2min|talk]]) 11:37, 4 November 2020 (UTC)
:Ooops! I found the sentence "... decides whether or not online user input such as email addresses are valid", and just inserted "syntactically" to indicate that no automaton can check whether a specified mailbox actually exists at the provider site. I wasn't aware of the complexity of address rules at [[Talk:Email_address#Complexity_of_email_addresses]] (the grammar there isn't even a regular one). I guess you suggest to replace this exmaple by a simpler one; and I agree with that. What about e.g. floating point numbers, integer numbers, or identifiers in some fixed programming language, or password rules (like "at least an upper case, a lower case letter, a digit, and a punctuation char must occur")? The available images at [[:commons:Category:Deterministic finite state automata]] are not too convincing for that purpose. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 13:03, 4 November 2020 (UTC)
::Identifiers in C are probably a nice example since you have a small alphabet (letters, digits, underscore). Password rules ("at least an upper case, a lower case letter, a digit, and a punctuation char must occur"), while simple to describe textually, would probably already be too big. (I think you need at least 1 + 4 + 6 + 4 + 1 states?) – [[User:Tea2min|Tea2min]] ([[User talk:Tea2min|talk]]) 15:17, 4 November 2020 (UTC)
== Section "Complete and incomplete" ==
> According to the above definition, deterministic finite automata are always complete: they define a transition for each state and each input symbol.
Isn't the description wrong? I understand the sentence to mean that each state must have a transition and the automaton must have a transition for each input symbol, but as far as I know, each state must have a transition for each input symbol.
My suggestion: "they define from each state a transition for each input symbol."
Sicro --- [[Special:Contributions/46.223.160.111|46.223.160.111]] ([[User talk:46.223.160.111|talk]]) 09:19, 24 October 2021 (UTC)
:{{done}} The old description is ok (if read as "given a state and an input symbol, a transition on them is defined"), but apparently can be misleading; your suggestion is more clear, so I changed the text. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 16:13, 24 October 2021 (UTC)
== Simplified diagram representation ==
It should be mentioned in this article that several transitions labeled with different input symbols leading from state A to state B can be combined into one transition to display the diagram in a simplified way. Technically, however, they are separate transitions, of course.
See at the top of page 3: https://www.cs.toronto.edu/~amir/teaching/csc236f15/materials/lec10.pdf
Sicro --- [[Special:Contributions/46.223.160.163|46.223.160.163]] ([[User talk:46.223.160.163|talk]]) 11:40, 28 October 2021 (UTC)
:I agree that this should be explained somewhere. Unfortunately, diagram notation isn't explained at all in this article. Instead it links to [[State diagram]] which handles the huge amount of existing variants; thus is is not that easy to find the right place to insert your information. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 12:29, 28 October 2021 (UTC)
| |||