Talk:Deterministic finite automaton

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Algebra

Technical flag[edit]

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? Ounsworth (talk) 18:50, 5 August 2010 (UTC)

What field?[edit]

To what field of human endeavor does this relate? Could someone put an introductory sentance in English for the rest of us? Thanks! ;) Mark Richards 06:21, 14 May 2004 (UTC)

Doesn't everyone know automata theory?  :-) -- jaredwf 07:27, 14 May 2004 (UTC)

Thanks Jaredwf Just a stupid question though - Finite State Machine says that it is related to 'computer science', while DFST points to 'Theory of computing'. Is this as it should be? Thanks! Mark Richards 15:39, 14 May 2004 (UTC)

I changed the finite state machine to say theory of computation, since theory of computation is a more exact answer. Thanks for noticing. -- jaredwf 15:46, 14 May 2004 (UTC)
Both are correct! Theory of Computation is a subdicipline of Computer Science. —Preceding unsigned comment added by Ben 1220 (talkcontribs) 09:36, 16 September 2009 (UTC)

symbols[edit]

The symbols used to describe the 5-tuple are inconsistent with those in Automata theory. Is it better to change to \langle Q, \Sigma, \delta, q_0, F\rangle? My textbook also uses these notations.

I'm in favor of this change. Pkirlin 06:47, 11 November 2005 (UTC)

  • 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. 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! 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. —Preceding unsigned comment added by 115.248.12.253 (talk) 06:23, 6 March 2010 (UTC)

Merge proposal[edit]

Oppose. Other articles reference FSMs without the presumption of determinism. --Ancheta Wis 02:25, 3 December 2005 (UTC)

Regular languages in relation to FSM[edit]

Can someone please explain the following entry in the article more. Now sure what this exactly is in relation to FSM (the article on regular language is just as perplexing).

The language of M can be described by the regular language given by this regular expression:

   1*(01*01*)*

yusufm 20:51, 13 April 2006 (UTC)

The section on regular language is the best place to parse this. The * is the Kleene Star mentioned in that article. So 1* is the set { epsilon, 1, 11, 111, 1111...) The Kleene star operator over a number of the alphabet symbols such as (01)* is the set { epsilon, 01, 0101, 010101...) Essentially it means none, one, or more of the items repeating.

DFA search image[edit]

DFA search mommy.svg

I've just fixed up the DFA image Image:DFA search mommy.svg so that it renders again. It's intended for string search algorithm but may be useful here. Dcoetzee 03:57, 2 April 2007 (UTC)

Missing paths - still deterministic?[edit]

The definition for DFA states that there should be one and only one transition for each pair of states and inputs. The definition for NFA only addresses the case of a single input leading to multiple, different states. What about the case where an input leads off to a "dummy state" that just loops back to itself on every input? If we just eliminate the dummy state and any inputs leading to it, does the diagram still represent a DFA? If not, is it an NFA? Or something else? Thanks, Maghnus 15:25, 29 October 2007 (UTC)

  • Ambigiuous: The description may be slightly ambiguous in that every pair of states and inputs should have exactly one transition. As I understand it, missing transitions are unacceptable for a DFA, and hence would be classes as an NFA. Pyrre (talk) 03:05, 23 December 2007 (UTC)
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. — Carl (CBM · talk) 03:21, 23 December 2007 (UTC)

Possible error in example[edit]

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

You are correct. It is bad language. Let me try a fix. (Ashutosh Gupta (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. 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. (Ashutosh Gupta (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. Raghunandan ma (talk) 06:53, 18 August 2011 (UTC)

Requested move[edit]

The following discussion is an archived discussion of a requested move. Please do not modify it. 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 Mike Cline (talk) 15:54, 3 December 2011 (UTC)



– These are more popular names of the automata theory concepts. Even within the articles the objects are referred as (non)deterministic finite automaton. Ashutosh Gupta (talk) 15:04, 25 November 2011 (UTC)

  • Support per nom. —Ruud 20:37, 25 November 2011 (UTC)
The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

DFA cannot recognize anbn?[edit]

The article states that:

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 anbn — some finite number of a's, followed by an equal number of b's.

I don't think that is correct. Consider the following state diagram:

S0a → S1b → S2 (ab)
S0a → S1a → S3b → S4b → S5 (aabb)
S0a → S1a → S3a → S6b → S7b → S8b → S9 (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 anbn. Granted, it will take a large number of states (perhaps on the order of 2n?) to embed the counting of a's and b's, but it still seems possible. Or did I miss something in the text? — Loadmaster (talk) 17:48, 27 January 2014 (UTC)

The wording is intended to describe the language \{ a^n b^n : n \in \mathbf{N} \} which has infinitely many words (indeed, exactly one of length 2n for every n≥0) and I think it does so. This is not a regular language, and cannot be recognised by a DFA. 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). — Loadmaster (talk) 22:01, 27 January 2014 (UTC)