Talk:Deterministic finite automaton

Computer science Start‑class High‑importance

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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Start‑class Mid‑priority

	Mathematics portal 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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

What field?

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)[reply]

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

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)[reply]

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)[reply]

Both are correct! Theory of Computation is a subdicipline of Computer Science. —Preceding unsigned comment added by Ben 1220 (talk • contribs) 09:36, 16 September 2009 (UTC)[reply]

symbols

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)[reply]

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)[reply]
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)[reply]

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)[reply]

Merge proposal

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

Regular languages in relation to FSM

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)[reply]

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

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)[reply]

Missing paths - still deterministic?

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)[reply]

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)[reply]

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)[reply]

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" Raghunandan ma (talk) 10:18, 16 August 2011 (UTC)[reply]

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

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)[reply]