Content deleted Content added
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: |
|||
| (10 intermediate revisions by 5 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=Start|
{{WikiProject Computer science|importance=high}}
{{WikiProject Mathematics|importance=mid}}
}}
==Technical flag==
Line 92 ⟶ 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 124 ⟶ 120:
:{{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)
| |||