Talk:Deterministic finite automaton: Difference between revisions

Revision as of 09:37, 16 September 2009

Latest revision as of 18:53, 31 January 2024

(40 intermediate revisions by 19 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

{{maths rating

{{WikiProject Computer science|importance=high}}

|field=algebra

{{WikiProject Mathematics|importance=mid}}

|class=Start

|vital=

|historical=

}}

==Technical flag==

I have rewritten the intro and added the section "Accept and Generate modes", both of which aim to be a non-technical introduction. Is this sufficient to remove the technical flag? [[User:Ounsworth|Ounsworth]] ([[User talk:Ounsworth|talk]]) 18:50, 5 August 2010 (UTC)

==What field?==

Line 25 ⟶ 24:

* '''agree'''. Me too. We should make this change. Using ''S'' conflicts with S for [[semigroup]]. Using ''A'' conflicts with ''A'' for ''Autamaton''. Using ''M'' conflicts with ''M'' for [[monoid]]. [[User:Linas|linas]] 14:17, 26 April 2007 (UTC)

* Done. I have at least two books that use this format, so I went ahead and made the change. If anyone disagrees, please comment here and let me know. Thanks! [[User:ThomasOwens|ThomasOwens]] ([[User talk:ThomasOwens|talk]]) 00:01, 11 December 2008 (UTC)

i m a student of computer science engineering and for me automata theory and formal languages is a very new subject. i m not being able to get hold of the subject properly. i cannot understand the subject. please suggest somthing. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/115.248.12.253|115.248.12.253]] ([[User talk:115.248.12.253|talk]]) 06:23, 6 March 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==Merge proposal==

Line 53:

:Missing paths are no big deal; the definition of what it means to run such an automaton will most likely say that if a path is missing, the automaton immediately halts (this can be simulated by adding an extra state and a new path to this state for each missing path in the original automaton). So long as there are never two paths on the same state/input pair, the automaton is deterministic. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 03:21, 23 December 2007 (UTC)

::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 ==

In the section "Advantages and Disadvantages", the example discribes the "bracket" language - i.e. properly paired brackets. This is not formally ''aⁿbⁿ'', as stated, but "Strings whose each prefix has more or equal a's than b's" [[User:Raghunandan ma|Raghunandan ma]] ([[User talk:Raghunandan ma|talk]]) 10:18, 16 August 2011 (UTC)

You are correct. It is bad language. Let me try a fix. ([[User:Ashutosh y0078|Ashutosh Gupta]] ([[User talk:Ashutosh y0078|talk]]) 13:34, 16 August 2011 (UTC))

Thank you. It looks better now. Also I suggest:

DFAs are equivalent in computing power to [[nondeterministic finite automata]] (NFAs). This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can do. Also, given an NFA, one can build a DFA that recognizes the same language as the NFA, although the DFA could have exponentially larger number of states than the NFA. [[User:Raghunandan ma|Raghunandan ma]] ([[User talk:Raghunandan ma|talk]]) 06:46, 17 August 2011 (UTC)

Your suggestion is good. Please add it yourself. I also suggest to cite [[powerset construction]] page for the algorithm that translates NFA into DFA. ([[User:Ashutosh y0078|Ashutosh Gupta]] ([[User talk:Ashutosh y0078|talk]]) 11:30, 17 August 2011 (UTC))

Have added this. Also made some small changes in the wording for union/intersection/complement at the beginning of this section. [[User:Raghunandan ma|Raghunandan ma]] ([[User talk:Raghunandan ma|talk]]) 06:53, 18 August 2011 (UTC)

== Requested move ==

<div class="boilerplate" style="background-color: #efe; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:RM top -->

:''The following discussion is an archived discussion 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 the talk page. No further edits should be made to this section. ''

The result of the move request was: '''Moves made, uncontested''' [[User:Mike Cline|Mike Cline]] ([[User talk:Mike Cline|talk]]) 15:54, 3 December 2011 (UTC)

----

* [[Deterministic finite-state machine]] → [[Deterministic finite automaton]]

* [[Nondeterministic finite-state machine]] → [[Nondeterministic finite automaton]]

– These are more popular names of the automata theory concepts. Even within the articles the objects are referred as (non)deterministic finite automaton.

[[User:Ashutosh y0078|Ashutosh Gupta]] ([[User talk:Ashutosh y0078|talk]]) 15:04, 25 November 2011 (UTC)

* '''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ⁿbⁿ''? ==

The [[Deterministic finite automaton#Advantages and disadvantages|article states]] that: {{quote|1=Many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. [...] Another simpler example is the language consisting of strings of the form ''a{{sup|n}}b{{sup|n}}'' — some finite number of ''a''&apos;s, followed by an equal number of ''b''&apos;s.}} I don't think that is correct. Consider the following state diagram:

:S{{sub|0}} → ''a'' → S{{sub|1}} → ''b'' → S{{sub|2}} (''ab'')

:S{{sub|0}} → ''a'' → S{{sub|1}} → ''a'' → S{{sub|3}} → ''b'' → S{{sub|4}} → ''b'' → S{{sub|5}} (''aabb'')

:S{{sub|0}} → ''a'' → S{{sub|1}} → ''a'' → S{{sub|3}} → ''a'' → S{{sub|6}} → ''b'' → S{{sub|7}} → ''b'' → S{{sub|8}} → ''b'' → S{{sub|9}} (''aaabbb'')

:And so forth.

As long as ''n'' is limited to a specific finite number, it looks like a DFA can indeed be built for the language ''a{{sup|n}}b{{sup|n}}''. Granted, it will take a large number of states (perhaps on the order of 2{{sup|''n''}}?) to embed the counting of ''a''&apos;s and ''b''&apos;s, but it still seems possible. Or did I miss something in the text? —&nbsp;[[User:Loadmaster|Loadmaster]] ([[User talk:Loadmaster|talk]]) 17:48, 27 January 2014 (UTC)

:The wording is intended to describe the language <math>\{ a^n b^n : n \in \mathbf{N} \}</math> which has infinitely many words (indeed, exactly one of length 2''n'' for every ''n''≥0) and I think it does so. This is not a regular language, and cannot be recognised by a DFA. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 19:38, 27 January 2014 (UTC)

::I thought so, but the wording was not clear, so I changed it (adding "arbitrary" to indicate an unbounded ''n''). —&nbsp;[[User:Loadmaster|Loadmaster]] ([[User talk:Loadmaster|talk]]) 22:01, 27 January 2014 (UTC)

== Removed "Accept and Generate Modes" section ==

I've removed the "Accept and Generate Modes" section on that grounds that it's original research by a defunct user. A search through my textbooks, university library search engine and Google didn't reveal anyone else who's talking about generate modes for DFAs. Even if that section isn't original research, we should consider whether it lends undue weight to a rarely-discussed type of DFA. [[User:Chip Wildon Forster|Chip Wildon Forster]] ([[User talk:Chip Wildon Forster|talk]]) 18:42, 31 January 2015 (UTC)

== 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">—&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)

:{{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)