Talk:Deterministic finite-state machine
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics rating: | Start Class | Mid Priority | Field: Algebra | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
Contents |
[edit] 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)
- 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)
[edit] symbols
The symbols used to describe the 5-tuple are inconsistent with those in Automata theory. Is it better to change to 
? 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)
[edit] Merge proposal
Oppose. Other articles reference FSMs without the presumption of determinism. --Ancheta Wis 02:25, 3 December 2005 (UTC)
[edit] 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)
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.
[edit] 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)
[edit] 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)
- 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)
