This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
Here is the FOLDOC article on this... if there is any information from here that can be merged into the main article, do so:
Finite State Machine <mathematics, algorithm, theory> (FSM or "Finite State Automaton", "transducer") An abstract machine consisting of a set of states (including the initial state), a set of input events, a set of output events, and a state transition function. The function takes the current state and an input event and returns the new set of output events and the next state. Some states may be designated as "terminal states". The state machine can also be viewed as a function which maps an ordered sequence of input events into a corresponding sequence of (sets of) output events.
A deterministic FSM (DFA) is one where the next state is uniquely determinied by a single input event. The next state of a nondeterministic FSM (NFA) depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in.
It is possible to automatically translate any nondeterministic FSM into a deterministic one which will produce the same output given the same input. Each state in the DFA represents the set of states the NFA might be in at a given time.
In a probabilistic FSM [or stochastic FSM], there is a predetermined probability of each next state given the current state and input (compare Markov chain).
The terms "acceptor" and "transducer" are used particularly in language theory where automata are often considered as abstract machines capable of recognising a language (certain sequences of input events). An acceptor has a single Boolean output and accepts or rejects the input sequence by outputting true or false respectively, whereas a transducer translates the input into a sequence of output events.
FSMs are used in computability theory and in some practical applications such as regular expressions and digital logic design.
See also state transition diagram, Turing Machine.
[J.H. Conway, "regular algebra and finite machines", 1971, Eds Chapman & Hall].
[S.C. Kleene, "Representation of events in nerve nets and finite automata", 1956, Automata Studies. Princeton].
[Hopcroft & Ullman, 1979, "Introduction to automata theory, languages and computations", Addison-Wesley].
[M. Crochemore "tranducters and repetitions", Theoritical. Comp. Sc. 46, 1986].— Preceding unsigned comment added by Anonymoues ( talk • contribs) 01:30, 27 October 2002 (UTC)
Ideally I think it would be best to have a seperate page for tools so that we could add some more (there are tons of them out there), sort them in categories and give a short description (IMHO having just the names is almost totally useless, the names and a link is already better but still not good enough).
I see at least three distinct categories (some programs would fall into more than one category but that's ok, I guess):
-- Gdementen ( talk | contribs) 13:36, 11 August 2004 (UTC)
Couldn't find a webpage for "fa (TCL)", so I removed it. Feel free to add it back IF you know of a link for it. -- Gdementen ( talk | contribs) 14:52, 11 August 2004 (UTC)
I don't feel strong enough to write a good article about the hardware applications now. Therefore I just moved the old content from the Implementation section to the Hardware application section making just small corrections. My changes in the Implementation section are focused on the definition and software applications, so let me know if you have any comments...
-- Thowa ( talk | contribs) 20:52, 18 December 2004 (UTC)
I replaced the new FSM logic by the old one, as it uses terms which are not mentioned/explained on the page: state generator, output generator etc. I wonder if this terms are correct in this context. Maybe some specific FSM modification was meant, but then I would write a new article, as this is not a classic FSM any more. For instance an FSM does not generate any states, but it is in a certain state and can change the state if certain (input) conditions are fulfilled.
-- Thowa ( talk | contribs) 19:49, 15 February 2005 (UTC)
Thowa ( talk | contribs) 20:44, 16 February 2005 (UTC): I wonder a little bit that you are so sceptic about the FSM logic figure. It shows exactly how an FSM behaves, so that everybody can understand. But paste into the discussion an other alternative diagram - as usually, everything can be improved - so we can discuss it. I would like to make a general statement about pages like this: I don't think the goal is to explain the entire FSM theory within one Wiki article: nobody can seriously try it. For this there are many books provided, we shall point to in the References section. The purpose of the article shall be to explain shortly to an interested reader what a FSM is and how can it be used in practise. This means of course that the current FSM article need some "rework". Besides an explanation how does it work (and this shall be possible to understand without spending few years studying maths) it shall mention of course that it can be used to build any kind of parser applications, but it shall also clearly state that the major applications are control systems in hardware and in software applications. This information for instance might be very useful for students many of them leaves the university believing that FSM is to build parser, just because it was used as a nice FSM example in some courses. The true potential of FSM is enormous and this is something this article shall communicate. To provide the "grey" theory is useless as nobody is interested to read it here as there are probably many thousand books which are much better if somebody really want to learn it. The article can be just a starting point.
If I understand correctly the comment of Deco, you would like to have a parser example instead of the provided door open/close example. I had to think about my salesman friend: I'm sure he will get an idea of how an FSM works if I tell him that a door can be closed or open and that this are the states of the door FSM. Then I mention the two obvious possible transitions: open to close, close to open and my friend learned something within few minutes. And if he is more interested I add an engine to control the door, which can be controlled by commands "close" and "open" and the actions problem is also clear. A parser is an academic example which would cover only few aspects of FSM and is probably to abstract to my friend. However I agree that it might be useful to put both examples, as we know everybody has his own individual preferred way of learning and this shall be probably taken into account by articles in Wikipedia.
I sorted the available content a little bit. The focus was on a general explanation for everybody rather than explaining details of the automata theory within a short article. For more information I extended the books list a little bit too. Any comments welcome. Thowa ( talk | contribs) 11:05, 26 February 2005 (UTC)
I removed the following contribution from GoodStuff:
There are two problems with it:
1. Mealy machine: the conditions which causes the input actions don't cause necessary a transition (it is possible but not obligatory). So a Mealy FSM can perform actions without changing the state. Besides this, we can use also transition actions which defines actions performed for a state transition but those are not known in a Mealy machine. Those actions can be replaced by input actions which conditions would also cause a transition, but this "work around" does not work in all cases.
2. Moore machine uses only entry actions, but it does not mean that in each state an entry action must be present.
Based on several comments and questions in the past, I found that the difference between Moore and Mealy as well as the sense and advantages of using a certain model are pretty confusing for many readers of the FSM article. Therefore I added a link to an external page, where a technical note about this topic accompanied by an executable example is presented. Maybe this is more helpful?
Thowa ( talk | contribs) 19:20, 25 April 2005 (UTC)
I removed the changes done by 81.208.61.96 because the information was misleading. He wrote:
The two most relevant things are incorrect:
1. Moore is not a subset of Mealy. Although it looks like this (Moore=output depends on state, Mealy=output depends on state and input), both models are independent. Moore means that there will be an action executed only if changing a state (i.e. we use only entry actions). Mealy is independent of state changes, because the actions are executed if a certain input is given and the FSM is in a certain state (i.e. we use only input actions). Have a look to the examples provided in the article: in figure 4 the FSM receives the input "close the door", so it starts the motor (input action), but it does not perform a transition to "Closed"
2. mixed models are typically used in software most probably, but in hardware mainly Moore model is used. So to keep this article generic, we better state "mixed models are often used", not more.
Thowa ( talk | contribs) 20:52, 15 March 2005 (UTC)
It presently says, for Mealy: "Output depends on input and state, i.e. the FSM uses only input actions."
Confusing!
It wasn't until I read this talk page that I understood how Mealy worked. That's because you wrote "Mealy is independent of state changes, because the actions are executed if a certain input is given and the FSM is in a certain state."
That made things much clearer.
The reason that what the article says is unclear, is because: Everything that happens in any FSM "depends on input and state."
Perhaps what is needed is a clarification of "Input Action"?
To be honest, I'm not sure what "input action" is either; "Execute the action dependent on input conditions." That can't mean that the current state is ignored, can it?
Perhaps it should say: "execute the action dependent on input conditions and immediate state, independent of transitions." It's not as short, but it's a lot clearer.
I feel that there should be a separate article on Moore and Mealy, to explain in more detail about how they work, and how they differ from the others.
LionKimbro ( talk | contribs) 20:22, 14 May 2005 (UTC)
Thanks for the responses!
I already made my change though: I made it say: "execute the action dependant on present state and input conditions"
LionKimbro ( talk | contribs) 20:01, 18 May 2005 (UTC)
This article seems to have a quite narrow focus in viewing finite state automata as machines with finite control state that react to events. Certainly for some applications, that view is sufficient, but finite automata are one of the most fundamental structures to computer science, and have a huge array of applications (usually with some generalizations, e.g. Markov chains can be viewed as stochastic finite automata, different logics can be interpreted using finite state automata over finite and/or infinite strings, properties in abstract algebra and term rewrite systems can be solved using finite tree automata, etc... At the same time, it is clear that a number of people have spent quite a bit of time on explaining finite automata in terms of these reactive state machines, and the explanation is those terms is quite good.
Perhaps there should be two articles, one on finite automata, the other on finite state machines. The finite automata article presents a high level overview of finite automata, how they are used, and why they are important. The finite state machine article gives a concrete model of a finite automata, specifically the one presented in this article. Before attempting to make such a large change, I thought I'd solicit feedback.
I've heard them called finite state transition networks, is this correct?— Preceding unsigned comment added by 139.222.214.202 ( talk) 08:26, 15 November 2005 (UTC)
Are automata diagrams an evolution of flow charts? How are the two related? Should we mention this? I've never heard them talked in relation to each other, so I wonder how many people have even taken that view. Is it a bad one to take? -- Rocifier 10:11, 14 November 2005 (UTC)
I would like to modify Fig. 2 ( Image:Fsm parsing word nice.jpg) in the article to include a transition from state 7 to state 6 and one from state 6 to itself. Any objections? Bergsten 14:00, 18 November 2005 (UTC)
(the anonymous editor User:67.169.25.19 added a proposal to merge with deterministic finite state machine to the article)
I suggest merging accept state into this article. Accepting states are a property of state machines, and I don't think that the accept state page will be able to be much more that a definition. MagiMaster 09:19, 10 July 2006 (UTC)
The following originally appears in the talk pages of Turing machine but I've copied it here closer to where it belongs. The notions of "discrete", "mappable to integers", "finite" are important to computational models such as Turing machines and somehow need to be emphasized more in this FSM article. wvbailey Wvbailey 14:18, 6 September 2006 (UTC)
Minsky (1967) spends about 20 pages giving us a definition of a "finite-state machine". It includes the following (italics in original):
In this context the word "state" is derived as follows:
There is another usage of "state" -- in mechanical dynamics theory. "State" here is the instantaneous snap-shot of an object relative to a frame of reference, but giving both its position (x, y, z) and velocity (dx/dt, dy/dt, dz/dt). The following is from pages 39-40 of Robert H. Cannon Jr, Dynamics of Physical Systems, McGraw-Hill Book Company, 1967.
Thus conventional, canonical state-machine analysis doesn't allow for "incoming" actions produced by a state. Input causes a change to a new state. "Outgoing" action, maybe -- at least in terms of "direction of change" shown by the arrow. Mealy machines represent a problem because [as noted above, repeated here]:
This notion of "finite time to traverse" comes up in the definition of algorithm -- in particular the work of Gurevich quoting Gandy.
And there really is no need for 'Mealy machines' anyway, because any 'Mealy' can be converted into a 'Moore' (cf Booth (1967), p. 960. Here he discusses this problem, that a 'Mealy' produces no output unless there's an input. He also notes that "a short time is allowed after the input symbol is applied before the output is observed", etc.
This is bizarre. No input e.g. (0,0,0,0) produces no output (0,0,0,0) but the machine is in a particular state, call it "B". As soon as an input is applied i.e. (0,1,0,0) the machine goes to a new state, call it "D". During its brief time going from B to D it produces an output (0,0,1,1). This appears as a pulse during the transition. If D is to sustain this pulse it must have a recirculating path back to itself i.e. (0,1,0,0) produces a recirculation back to D and maintains (0,0,1,1). Clearly, this is not trival stuff.
There appears to be a kind of pseudo-state used by software folks -- but you can always atomize this so-called "state of many colors" into true states each of one color. I've questioned this on a talk page. Over the years I've both written and debugged thousands of lines of pseudo-state-machine software -- thousands of pieces of equipment use the code-- and I have no idea what the fuck the article is talking about. Wvbailey 14:29, 17 August 2006 (UTC)
There is a problem with starting line of article. Basically it states that actions are fundamental part of automata and than it proceeds with entry/exit/input/transition actions. This isn’t right. Actually it is completely wrong. Automata with actions, like more or mealy machines or workflows in general, are higher level abstractions of state automata. Actions are cool concept but they are convenience within automata; they do not present fundamental property of state machines. Fundamental property is transition table. Stating that automata have actions is plain wrong. This article also fails to mention that fundamental automat is DFA. It doesn’t state that fundamental property of automata is state transition table (that is states and graph they make). All automata can be presented as DFA, and if there is some *automata* which can’t be transformed to DFA than it isn’t automata. That’s why they are called state machines in the first place. This article doesn’t state that and it doesn’t make proper distinction between fundamental parts of automata and conveniences which we use to make them easier to handle.
A finite state machine is an atomized model of a type of "computation": with discrete, finite and "static-between-moves" behaviors (see the section above for definitions of "state"). The canonical FSM model is nothing more than a single lookup table with a memory feeding back to the lookup table, inputs into the lookup table, and outputs from the lookup table. Whether the memory is clocked or not depends on what the designer is up to. Clocking helps eliminate evil behaviors such as "races" etc. Every single type of real and model FSM (e.g. decimal counters) can be redrawn to "look like" the canonical model.
Such an atomized model will not have all these different kinds of input and output behaviors.
A particular state can have exactly one "behavior" (output), and one behavior only. This is virtually the definition of "the state". Otherwise it can be further atomized into more states (QED). Even a "behavior on exit/transition" (e.g. a pulse) can be further atomized into two states and the model refined. A transition occurs 'very fast' and if it doesn't and a glitch occurs (due to a delay) then the delay must become part of the FSM model and reflect an added state (or states).
Someone needs to reference the source(s) that claim all these types of input and output actions. Otherwise the intro will have to be reworked. I have not seen all these actions asserted in any classical engineering or theoretical computer-science texts. Wvbailey 14:48, 6 September 2006 (UTC)
To write an article within an encyclopaedia you shall compare multiple books and have experience in several different use cases, not only hardware design (based on your remarks, I assume you are a “hardware man”)
It is an encyclopaedia article and you cannot expect that the reader is familiar with all this stuff. People, who know FSM read books to learn more, not short explanation within an encyclopaedia. As mentioned above, those terms don’t fit here anyway. Thowa 07:45, 7 September 2006 (UTC)
I'm also using FSM technology for years mainly for SW design but within my team there is also a lot of HW design where this technlogy is used every day. So this is a bad argument as well as using own published achievements - I could also provide a long list (publications, books, patents). As said above, the intention of this article is different from what you expect. Thowa 20:22, 13 September 2006 (UTC)
What I suggest is that we work together in a constructive way, rather than against each other. Because I am just as capable of reverting as you are. Wvbailey 17:46, 7 September 2006 (UTC)
Wikipedia should explain some basic concepts, and direct by links to special cases or exotic derivations.
The origin of a finite state machine comes from the Automata Theory, well known in some circles for over half a century, and the concept is presented in that way in the Wikipedia article.
The basic definitions should not be expanded or completed by special definitions found in some books which deal with a specific variety or application of the f.s.m.. A good example is the concept of a state. The strict Automata Theory definition is: "A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment".
Of course the word state has several other meanings in other contexts but these are irrelevant to presention of the the finite state machine definition.
Another example is the concept of actions or outputs. In general finite state machines are used for control purposes, i.e. that they define some actions (a term used in software) or outputs (a term used in hardware) to be done at certain moments, in certain states. Among others finite state machines are used to detect specific sequences of inputs: they are then called parsers and they do not employ actions or outputs. A parser is then a specific variant of a finite state machine and there is a link in the Wikipedia article for interested persons. It seems to be reasonable to discuss a general model of a finite state machine and then to indicate variants that do not use all possible features and are known under names that have evolved in the past like parser, Mealy, Moore, Turing, push-down automaton, etc. The variants of the finite state machine sometimes use their own terminology; adding such specific and non-standard terminolgy while discussing basic definitions would not simplify the article but produce chaos that will not help people who are searching for basic definitions in Wikipedia. 84.164.238.117 18:55, 7 September 2006 (UTC)
OK. Consider a "real" computer. Let M, N be fixed positive integers. At any given time the computer is in a state s(i) such that 0 <= s(i) < N. Let the input at time i be denoted x(i), where 0 <= x(i) < M. Each "next" state is a mathematical function of the current state and the input: s(i+1) = f(s(i), x(i)). But this is just an FSM. Thus the FSM is a more realistic model for a real computer than the Turing machine. Yet the Turing machine is preferred in CS theory as the model for the computer. This makes sense, since FSMs in practice must have an astronomically large number of states to "run" many algorithms. So, is there some sort of general result that shows why the TM is better than the FSM as a computing model? Or am I completely wrong in my analysis? - Connelly 08:28, 9 October 2005 (UTC)
Should'nt figure 1 have a closed state ? Both states are opened. Lacouf 21:21, 29 October 2007 (UTC)
I think so. That confused me too. I'm not knowledgable enough about FSA to be confident that I'm right though. —Preceding unsigned comment added by 149.155.96.5 ( talk) 10:25, 2 November 2007 (UTC)
Of course it is wrong, it should be replaced with the gif again ( 80.79.80.249 12:57, 2 November 2007 (UTC))
List of state machine CAD tools is up for deletion. Since the list started on this page, I thought some people might care if its gone. Here is where the deletion will be decided Wikipedia:Articles for deletion/List of state machine CAD tools. Fresheneesz ( talk) 06:17, 7 December 2007 (UTC)
Why is the reference section abnormally large? -- AllyUnion (talk) 23:14, 21 February 2008 (UTC)
Figure 1 is discussed in the section comparing Moore machines and Mealy machines, but since it's at the top of the page, it's hard to follow the explanation. 72.197.74.80 ( talk) 02:15, 31 July 2008 (UTC)
The problem is much easier to understand for those, who understand the aestetics of the primary cycle of texno with knowledge of classical music, whatever is considered (and re-celebrated) as classical. :) —Preceding unsigned comment added by 213.191.111.80 ( talk) 19:28, 2 August 2008 (UTC)
I find the references from this section which use message terminology much clearer and more consistent than this article.
I'm suggesting use of 'message', 'input message' or 'output message' in place of 'input', 'output', 'condition', 'action' etc. This emphasizes the importance of time and sequence in the theory. For example, the distinction between Deterministic and Non-deterministic FSMs is quite incomprehensible in the article as it stands but can be clearly explained in message terms. A non-deterministic FSM is one in which the state may depend on more than one input message, so the state is indeterminate from the arrival of the first message to the arrival of the last. This also makes it easy to explain why a non-deterministic FSM can be converted to a deterministic one - intermediate states are added for all possible message sequences which provides the machine with a message memory and representations for the previously indeterminate states.
In these terms, a recognizer receives a sequence of input messages each representing a single character. When the required sub-sequence has been recognized, it dispatches an output message signaling this fact. As far as I can see message terminology is generic and covers all FSM variants and usages so avoiding the confusion of multiple domain specific terms like 'string', 'input condition' and 'accepting state'.
JohnAHind ( talk) 17:40, 6 February 2008 (UTC)
I do agree w/ the wiki pages discussing "Moore machine" & "Melee machine".
a Mealy machine is a finite state transducer that generates an output based on its current state and input.
a Moore machine is a finite state transducer where the outputs are determined by the current state alone (and do not depend directly on the input).
— Preceding
unsigned comment added by
199.106.103.254 (
talk) 00:06, 05 June 2009 (UTC)
Can anybody tell me why the title is "Finite-state machine" while the text says "finite state machine"? —Preceding unsigned comment added by 79.211.180.141 ( talk) 22:43, 8 November 2009 (UTC)
They are all correct. It is an interesting question, and I hope it will be an interesting answer.
Nist says finite state machine is a kind of state machine or state automaton. Notice how the word state remains steady in the middle of a three-word phrase despite the loss of its first word finite (which can just disappear) or the morphing of its last word machine into automaton.
There are three meanings for "state":
The third meaning of state relates to the diagram; the first two to the machine. The confusion arises for two-part reason that each of the quantities of states are all in fixed relation, and so finite may refer to any of the three and infer the others. A person may have one concept on their mind, when they read or write such a hyper-hyphenate-able phrase—or not—only three will do to understand the answer.
Each of the quantities of states are all in fixed relation because the quantity of state-positions in the diagram is related to the quantity of state-points measured internal to the machine is related to the quantity of values in the measurement range of each point.
Therefore, finite can refer to any one of those quantities. And those quantities may be lumped together in any hyphenated way, because finite applies to state in general. Finite refers to
Subset here implies a state is a set, and a subset is a member of that set. Finite also means closed as in set theory, where every operation on a member results in another member. Funny thing is, member can refer to either a diagram or measurement point, and it is still true to say "every operation on a member results in another member". But wait! There is a forth set. Each path through the state-diagram is a meta-temporal temporal set!
The world is plumb full of it. Just stick up your thumb. Thank you for asking, for now I know. The remaining is the edited phase-of-confusion I waded through.
A Google search shows that the following universities say "finite-state machine":
Quoting Freedman and Ince's "Active Java", p77
An object is something which has a state... the object paradigm is universal.
David J Comer in his book "Digital Logic and State Machine Design" says
...the practical meaning of the existence of states [is a ] set of values measured at various points in a circuit. p.240
(Italics and bolding are mine.) That's one state containing several measurements. And he says:
...it may run through a different sequence of states before returning to the starting state, the system has a finite number of such paths and repetition in inevitable. (p.242)
Obviously finite refers to paths and the three states.
For now, guess what? I make a redirect page to this one, and keep the title. Cpiral Cpiral 05:31, 30 December 2009 (UTC)
Rewrote the intro. Need 2nd opinion for removal of the following tag { { tooshort } } . M!uqomzXb ( talk) 12:03, 4 June 2010 (UTC)
It seems to me that the definition of an "Acceptor" or "recognizer" falls under the definition of a transducer. Why are these written as two different types.. I thought Mealy and Moore machines were the two different types of state machines - as all state machines fall under either one of those categories. Fresheneesz 04:23, 13 December 2006 (UTC)
The section on optimization could really use some further explination! It is practically useless as it stands now. Meekohi 01:52, 30 August 2006 (UTC)
Optimization algorithms for finite state machines are complex and interesting. They should probably have their own pages. Markminn07 ( talk) 04:46, 29 August 2008 (UTC)
State machine is the device readily implemented in a vast number of techniques. THIS IS NOT A MODEL! This is a "tangible" device. This is implementation of a model, not the model itself. Model is always missing some details, while state machine is absolutely concrete, no matter in what way you implement it, in C++ or in VHDL (I did both plenty times). State machine exists as a digital electronics device, the same way as trigger or register; I hope nobody here will say a register or trigger is A MODEL!!! State machines exist in form of software components. Who will say the working software is a model??? Oh my... Neonil ( talk) 14:14, 8 July 2009 (UTC)
I am sorry, but FSM is a model. A register is not a model, obviously, as well it is not a FSM. A register can be modeled in form of FSM. A FSM (that models a register) does not deal with the delays, voltage, mass, material, size, color of the register. More over FSM does not describe full behavior of the device it models (e.g. FSM can not describe the multivibrator circuit on triggers). So, I am sorry I must disappoint you, FSM is a model. (Vladimir E. Zyubin, PhD in CS) Zyubin ( talk) 13:56, 20 November 2011 (UTC)
Was it Alan Turing who invented the concept of a finite state machine by creating the example we now call Turing machines in his famous paper about the decision problem? Jfgrcar ( talk) 04:02, 18 February 2010 (UTC)
hey there! Why is the language link for turkish ends with http://tr.wikipedia.org/wiki/Sonlu_durum_makinas%C4%B1 weird characters? thanks. —Preceding unsigned comment added by 95.90.78.57 ( talk) 16:16, 1 March 2011 (UTC)
This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
Here is the FOLDOC article on this... if there is any information from here that can be merged into the main article, do so:
Finite State Machine <mathematics, algorithm, theory> (FSM or "Finite State Automaton", "transducer") An abstract machine consisting of a set of states (including the initial state), a set of input events, a set of output events, and a state transition function. The function takes the current state and an input event and returns the new set of output events and the next state. Some states may be designated as "terminal states". The state machine can also be viewed as a function which maps an ordered sequence of input events into a corresponding sequence of (sets of) output events.
A deterministic FSM (DFA) is one where the next state is uniquely determinied by a single input event. The next state of a nondeterministic FSM (NFA) depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in.
It is possible to automatically translate any nondeterministic FSM into a deterministic one which will produce the same output given the same input. Each state in the DFA represents the set of states the NFA might be in at a given time.
In a probabilistic FSM [or stochastic FSM], there is a predetermined probability of each next state given the current state and input (compare Markov chain).
The terms "acceptor" and "transducer" are used particularly in language theory where automata are often considered as abstract machines capable of recognising a language (certain sequences of input events). An acceptor has a single Boolean output and accepts or rejects the input sequence by outputting true or false respectively, whereas a transducer translates the input into a sequence of output events.
FSMs are used in computability theory and in some practical applications such as regular expressions and digital logic design.
See also state transition diagram, Turing Machine.
[J.H. Conway, "regular algebra and finite machines", 1971, Eds Chapman & Hall].
[S.C. Kleene, "Representation of events in nerve nets and finite automata", 1956, Automata Studies. Princeton].
[Hopcroft & Ullman, 1979, "Introduction to automata theory, languages and computations", Addison-Wesley].
[M. Crochemore "tranducters and repetitions", Theoritical. Comp. Sc. 46, 1986].— Preceding unsigned comment added by Anonymoues ( talk • contribs) 01:30, 27 October 2002 (UTC)
Ideally I think it would be best to have a seperate page for tools so that we could add some more (there are tons of them out there), sort them in categories and give a short description (IMHO having just the names is almost totally useless, the names and a link is already better but still not good enough).
I see at least three distinct categories (some programs would fall into more than one category but that's ok, I guess):
-- Gdementen ( talk | contribs) 13:36, 11 August 2004 (UTC)
Couldn't find a webpage for "fa (TCL)", so I removed it. Feel free to add it back IF you know of a link for it. -- Gdementen ( talk | contribs) 14:52, 11 August 2004 (UTC)
I don't feel strong enough to write a good article about the hardware applications now. Therefore I just moved the old content from the Implementation section to the Hardware application section making just small corrections. My changes in the Implementation section are focused on the definition and software applications, so let me know if you have any comments...
-- Thowa ( talk | contribs) 20:52, 18 December 2004 (UTC)
I replaced the new FSM logic by the old one, as it uses terms which are not mentioned/explained on the page: state generator, output generator etc. I wonder if this terms are correct in this context. Maybe some specific FSM modification was meant, but then I would write a new article, as this is not a classic FSM any more. For instance an FSM does not generate any states, but it is in a certain state and can change the state if certain (input) conditions are fulfilled.
-- Thowa ( talk | contribs) 19:49, 15 February 2005 (UTC)
Thowa ( talk | contribs) 20:44, 16 February 2005 (UTC): I wonder a little bit that you are so sceptic about the FSM logic figure. It shows exactly how an FSM behaves, so that everybody can understand. But paste into the discussion an other alternative diagram - as usually, everything can be improved - so we can discuss it. I would like to make a general statement about pages like this: I don't think the goal is to explain the entire FSM theory within one Wiki article: nobody can seriously try it. For this there are many books provided, we shall point to in the References section. The purpose of the article shall be to explain shortly to an interested reader what a FSM is and how can it be used in practise. This means of course that the current FSM article need some "rework". Besides an explanation how does it work (and this shall be possible to understand without spending few years studying maths) it shall mention of course that it can be used to build any kind of parser applications, but it shall also clearly state that the major applications are control systems in hardware and in software applications. This information for instance might be very useful for students many of them leaves the university believing that FSM is to build parser, just because it was used as a nice FSM example in some courses. The true potential of FSM is enormous and this is something this article shall communicate. To provide the "grey" theory is useless as nobody is interested to read it here as there are probably many thousand books which are much better if somebody really want to learn it. The article can be just a starting point.
If I understand correctly the comment of Deco, you would like to have a parser example instead of the provided door open/close example. I had to think about my salesman friend: I'm sure he will get an idea of how an FSM works if I tell him that a door can be closed or open and that this are the states of the door FSM. Then I mention the two obvious possible transitions: open to close, close to open and my friend learned something within few minutes. And if he is more interested I add an engine to control the door, which can be controlled by commands "close" and "open" and the actions problem is also clear. A parser is an academic example which would cover only few aspects of FSM and is probably to abstract to my friend. However I agree that it might be useful to put both examples, as we know everybody has his own individual preferred way of learning and this shall be probably taken into account by articles in Wikipedia.
I sorted the available content a little bit. The focus was on a general explanation for everybody rather than explaining details of the automata theory within a short article. For more information I extended the books list a little bit too. Any comments welcome. Thowa ( talk | contribs) 11:05, 26 February 2005 (UTC)
I removed the following contribution from GoodStuff:
There are two problems with it:
1. Mealy machine: the conditions which causes the input actions don't cause necessary a transition (it is possible but not obligatory). So a Mealy FSM can perform actions without changing the state. Besides this, we can use also transition actions which defines actions performed for a state transition but those are not known in a Mealy machine. Those actions can be replaced by input actions which conditions would also cause a transition, but this "work around" does not work in all cases.
2. Moore machine uses only entry actions, but it does not mean that in each state an entry action must be present.
Based on several comments and questions in the past, I found that the difference between Moore and Mealy as well as the sense and advantages of using a certain model are pretty confusing for many readers of the FSM article. Therefore I added a link to an external page, where a technical note about this topic accompanied by an executable example is presented. Maybe this is more helpful?
Thowa ( talk | contribs) 19:20, 25 April 2005 (UTC)
I removed the changes done by 81.208.61.96 because the information was misleading. He wrote:
The two most relevant things are incorrect:
1. Moore is not a subset of Mealy. Although it looks like this (Moore=output depends on state, Mealy=output depends on state and input), both models are independent. Moore means that there will be an action executed only if changing a state (i.e. we use only entry actions). Mealy is independent of state changes, because the actions are executed if a certain input is given and the FSM is in a certain state (i.e. we use only input actions). Have a look to the examples provided in the article: in figure 4 the FSM receives the input "close the door", so it starts the motor (input action), but it does not perform a transition to "Closed"
2. mixed models are typically used in software most probably, but in hardware mainly Moore model is used. So to keep this article generic, we better state "mixed models are often used", not more.
Thowa ( talk | contribs) 20:52, 15 March 2005 (UTC)
It presently says, for Mealy: "Output depends on input and state, i.e. the FSM uses only input actions."
Confusing!
It wasn't until I read this talk page that I understood how Mealy worked. That's because you wrote "Mealy is independent of state changes, because the actions are executed if a certain input is given and the FSM is in a certain state."
That made things much clearer.
The reason that what the article says is unclear, is because: Everything that happens in any FSM "depends on input and state."
Perhaps what is needed is a clarification of "Input Action"?
To be honest, I'm not sure what "input action" is either; "Execute the action dependent on input conditions." That can't mean that the current state is ignored, can it?
Perhaps it should say: "execute the action dependent on input conditions and immediate state, independent of transitions." It's not as short, but it's a lot clearer.
I feel that there should be a separate article on Moore and Mealy, to explain in more detail about how they work, and how they differ from the others.
LionKimbro ( talk | contribs) 20:22, 14 May 2005 (UTC)
Thanks for the responses!
I already made my change though: I made it say: "execute the action dependant on present state and input conditions"
LionKimbro ( talk | contribs) 20:01, 18 May 2005 (UTC)
This article seems to have a quite narrow focus in viewing finite state automata as machines with finite control state that react to events. Certainly for some applications, that view is sufficient, but finite automata are one of the most fundamental structures to computer science, and have a huge array of applications (usually with some generalizations, e.g. Markov chains can be viewed as stochastic finite automata, different logics can be interpreted using finite state automata over finite and/or infinite strings, properties in abstract algebra and term rewrite systems can be solved using finite tree automata, etc... At the same time, it is clear that a number of people have spent quite a bit of time on explaining finite automata in terms of these reactive state machines, and the explanation is those terms is quite good.
Perhaps there should be two articles, one on finite automata, the other on finite state machines. The finite automata article presents a high level overview of finite automata, how they are used, and why they are important. The finite state machine article gives a concrete model of a finite automata, specifically the one presented in this article. Before attempting to make such a large change, I thought I'd solicit feedback.
I've heard them called finite state transition networks, is this correct?— Preceding unsigned comment added by 139.222.214.202 ( talk) 08:26, 15 November 2005 (UTC)
Are automata diagrams an evolution of flow charts? How are the two related? Should we mention this? I've never heard them talked in relation to each other, so I wonder how many people have even taken that view. Is it a bad one to take? -- Rocifier 10:11, 14 November 2005 (UTC)
I would like to modify Fig. 2 ( Image:Fsm parsing word nice.jpg) in the article to include a transition from state 7 to state 6 and one from state 6 to itself. Any objections? Bergsten 14:00, 18 November 2005 (UTC)
(the anonymous editor User:67.169.25.19 added a proposal to merge with deterministic finite state machine to the article)
I suggest merging accept state into this article. Accepting states are a property of state machines, and I don't think that the accept state page will be able to be much more that a definition. MagiMaster 09:19, 10 July 2006 (UTC)
The following originally appears in the talk pages of Turing machine but I've copied it here closer to where it belongs. The notions of "discrete", "mappable to integers", "finite" are important to computational models such as Turing machines and somehow need to be emphasized more in this FSM article. wvbailey Wvbailey 14:18, 6 September 2006 (UTC)
Minsky (1967) spends about 20 pages giving us a definition of a "finite-state machine". It includes the following (italics in original):
In this context the word "state" is derived as follows:
There is another usage of "state" -- in mechanical dynamics theory. "State" here is the instantaneous snap-shot of an object relative to a frame of reference, but giving both its position (x, y, z) and velocity (dx/dt, dy/dt, dz/dt). The following is from pages 39-40 of Robert H. Cannon Jr, Dynamics of Physical Systems, McGraw-Hill Book Company, 1967.
Thus conventional, canonical state-machine analysis doesn't allow for "incoming" actions produced by a state. Input causes a change to a new state. "Outgoing" action, maybe -- at least in terms of "direction of change" shown by the arrow. Mealy machines represent a problem because [as noted above, repeated here]:
This notion of "finite time to traverse" comes up in the definition of algorithm -- in particular the work of Gurevich quoting Gandy.
And there really is no need for 'Mealy machines' anyway, because any 'Mealy' can be converted into a 'Moore' (cf Booth (1967), p. 960. Here he discusses this problem, that a 'Mealy' produces no output unless there's an input. He also notes that "a short time is allowed after the input symbol is applied before the output is observed", etc.
This is bizarre. No input e.g. (0,0,0,0) produces no output (0,0,0,0) but the machine is in a particular state, call it "B". As soon as an input is applied i.e. (0,1,0,0) the machine goes to a new state, call it "D". During its brief time going from B to D it produces an output (0,0,1,1). This appears as a pulse during the transition. If D is to sustain this pulse it must have a recirculating path back to itself i.e. (0,1,0,0) produces a recirculation back to D and maintains (0,0,1,1). Clearly, this is not trival stuff.
There appears to be a kind of pseudo-state used by software folks -- but you can always atomize this so-called "state of many colors" into true states each of one color. I've questioned this on a talk page. Over the years I've both written and debugged thousands of lines of pseudo-state-machine software -- thousands of pieces of equipment use the code-- and I have no idea what the fuck the article is talking about. Wvbailey 14:29, 17 August 2006 (UTC)
There is a problem with starting line of article. Basically it states that actions are fundamental part of automata and than it proceeds with entry/exit/input/transition actions. This isn’t right. Actually it is completely wrong. Automata with actions, like more or mealy machines or workflows in general, are higher level abstractions of state automata. Actions are cool concept but they are convenience within automata; they do not present fundamental property of state machines. Fundamental property is transition table. Stating that automata have actions is plain wrong. This article also fails to mention that fundamental automat is DFA. It doesn’t state that fundamental property of automata is state transition table (that is states and graph they make). All automata can be presented as DFA, and if there is some *automata* which can’t be transformed to DFA than it isn’t automata. That’s why they are called state machines in the first place. This article doesn’t state that and it doesn’t make proper distinction between fundamental parts of automata and conveniences which we use to make them easier to handle.
A finite state machine is an atomized model of a type of "computation": with discrete, finite and "static-between-moves" behaviors (see the section above for definitions of "state"). The canonical FSM model is nothing more than a single lookup table with a memory feeding back to the lookup table, inputs into the lookup table, and outputs from the lookup table. Whether the memory is clocked or not depends on what the designer is up to. Clocking helps eliminate evil behaviors such as "races" etc. Every single type of real and model FSM (e.g. decimal counters) can be redrawn to "look like" the canonical model.
Such an atomized model will not have all these different kinds of input and output behaviors.
A particular state can have exactly one "behavior" (output), and one behavior only. This is virtually the definition of "the state". Otherwise it can be further atomized into more states (QED). Even a "behavior on exit/transition" (e.g. a pulse) can be further atomized into two states and the model refined. A transition occurs 'very fast' and if it doesn't and a glitch occurs (due to a delay) then the delay must become part of the FSM model and reflect an added state (or states).
Someone needs to reference the source(s) that claim all these types of input and output actions. Otherwise the intro will have to be reworked. I have not seen all these actions asserted in any classical engineering or theoretical computer-science texts. Wvbailey 14:48, 6 September 2006 (UTC)
To write an article within an encyclopaedia you shall compare multiple books and have experience in several different use cases, not only hardware design (based on your remarks, I assume you are a “hardware man”)
It is an encyclopaedia article and you cannot expect that the reader is familiar with all this stuff. People, who know FSM read books to learn more, not short explanation within an encyclopaedia. As mentioned above, those terms don’t fit here anyway. Thowa 07:45, 7 September 2006 (UTC)
I'm also using FSM technology for years mainly for SW design but within my team there is also a lot of HW design where this technlogy is used every day. So this is a bad argument as well as using own published achievements - I could also provide a long list (publications, books, patents). As said above, the intention of this article is different from what you expect. Thowa 20:22, 13 September 2006 (UTC)
What I suggest is that we work together in a constructive way, rather than against each other. Because I am just as capable of reverting as you are. Wvbailey 17:46, 7 September 2006 (UTC)
Wikipedia should explain some basic concepts, and direct by links to special cases or exotic derivations.
The origin of a finite state machine comes from the Automata Theory, well known in some circles for over half a century, and the concept is presented in that way in the Wikipedia article.
The basic definitions should not be expanded or completed by special definitions found in some books which deal with a specific variety or application of the f.s.m.. A good example is the concept of a state. The strict Automata Theory definition is: "A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment".
Of course the word state has several other meanings in other contexts but these are irrelevant to presention of the the finite state machine definition.
Another example is the concept of actions or outputs. In general finite state machines are used for control purposes, i.e. that they define some actions (a term used in software) or outputs (a term used in hardware) to be done at certain moments, in certain states. Among others finite state machines are used to detect specific sequences of inputs: they are then called parsers and they do not employ actions or outputs. A parser is then a specific variant of a finite state machine and there is a link in the Wikipedia article for interested persons. It seems to be reasonable to discuss a general model of a finite state machine and then to indicate variants that do not use all possible features and are known under names that have evolved in the past like parser, Mealy, Moore, Turing, push-down automaton, etc. The variants of the finite state machine sometimes use their own terminology; adding such specific and non-standard terminolgy while discussing basic definitions would not simplify the article but produce chaos that will not help people who are searching for basic definitions in Wikipedia. 84.164.238.117 18:55, 7 September 2006 (UTC)
OK. Consider a "real" computer. Let M, N be fixed positive integers. At any given time the computer is in a state s(i) such that 0 <= s(i) < N. Let the input at time i be denoted x(i), where 0 <= x(i) < M. Each "next" state is a mathematical function of the current state and the input: s(i+1) = f(s(i), x(i)). But this is just an FSM. Thus the FSM is a more realistic model for a real computer than the Turing machine. Yet the Turing machine is preferred in CS theory as the model for the computer. This makes sense, since FSMs in practice must have an astronomically large number of states to "run" many algorithms. So, is there some sort of general result that shows why the TM is better than the FSM as a computing model? Or am I completely wrong in my analysis? - Connelly 08:28, 9 October 2005 (UTC)
Should'nt figure 1 have a closed state ? Both states are opened. Lacouf 21:21, 29 October 2007 (UTC)
I think so. That confused me too. I'm not knowledgable enough about FSA to be confident that I'm right though. —Preceding unsigned comment added by 149.155.96.5 ( talk) 10:25, 2 November 2007 (UTC)
Of course it is wrong, it should be replaced with the gif again ( 80.79.80.249 12:57, 2 November 2007 (UTC))
List of state machine CAD tools is up for deletion. Since the list started on this page, I thought some people might care if its gone. Here is where the deletion will be decided Wikipedia:Articles for deletion/List of state machine CAD tools. Fresheneesz ( talk) 06:17, 7 December 2007 (UTC)
Why is the reference section abnormally large? -- AllyUnion (talk) 23:14, 21 February 2008 (UTC)
Figure 1 is discussed in the section comparing Moore machines and Mealy machines, but since it's at the top of the page, it's hard to follow the explanation. 72.197.74.80 ( talk) 02:15, 31 July 2008 (UTC)
The problem is much easier to understand for those, who understand the aestetics of the primary cycle of texno with knowledge of classical music, whatever is considered (and re-celebrated) as classical. :) —Preceding unsigned comment added by 213.191.111.80 ( talk) 19:28, 2 August 2008 (UTC)
I find the references from this section which use message terminology much clearer and more consistent than this article.
I'm suggesting use of 'message', 'input message' or 'output message' in place of 'input', 'output', 'condition', 'action' etc. This emphasizes the importance of time and sequence in the theory. For example, the distinction between Deterministic and Non-deterministic FSMs is quite incomprehensible in the article as it stands but can be clearly explained in message terms. A non-deterministic FSM is one in which the state may depend on more than one input message, so the state is indeterminate from the arrival of the first message to the arrival of the last. This also makes it easy to explain why a non-deterministic FSM can be converted to a deterministic one - intermediate states are added for all possible message sequences which provides the machine with a message memory and representations for the previously indeterminate states.
In these terms, a recognizer receives a sequence of input messages each representing a single character. When the required sub-sequence has been recognized, it dispatches an output message signaling this fact. As far as I can see message terminology is generic and covers all FSM variants and usages so avoiding the confusion of multiple domain specific terms like 'string', 'input condition' and 'accepting state'.
JohnAHind ( talk) 17:40, 6 February 2008 (UTC)
I do agree w/ the wiki pages discussing "Moore machine" & "Melee machine".
a Mealy machine is a finite state transducer that generates an output based on its current state and input.
a Moore machine is a finite state transducer where the outputs are determined by the current state alone (and do not depend directly on the input).
— Preceding
unsigned comment added by
199.106.103.254 (
talk) 00:06, 05 June 2009 (UTC)
Can anybody tell me why the title is "Finite-state machine" while the text says "finite state machine"? —Preceding unsigned comment added by 79.211.180.141 ( talk) 22:43, 8 November 2009 (UTC)
They are all correct. It is an interesting question, and I hope it will be an interesting answer.
Nist says finite state machine is a kind of state machine or state automaton. Notice how the word state remains steady in the middle of a three-word phrase despite the loss of its first word finite (which can just disappear) or the morphing of its last word machine into automaton.
There are three meanings for "state":
The third meaning of state relates to the diagram; the first two to the machine. The confusion arises for two-part reason that each of the quantities of states are all in fixed relation, and so finite may refer to any of the three and infer the others. A person may have one concept on their mind, when they read or write such a hyper-hyphenate-able phrase—or not—only three will do to understand the answer.
Each of the quantities of states are all in fixed relation because the quantity of state-positions in the diagram is related to the quantity of state-points measured internal to the machine is related to the quantity of values in the measurement range of each point.
Therefore, finite can refer to any one of those quantities. And those quantities may be lumped together in any hyphenated way, because finite applies to state in general. Finite refers to
Subset here implies a state is a set, and a subset is a member of that set. Finite also means closed as in set theory, where every operation on a member results in another member. Funny thing is, member can refer to either a diagram or measurement point, and it is still true to say "every operation on a member results in another member". But wait! There is a forth set. Each path through the state-diagram is a meta-temporal temporal set!
The world is plumb full of it. Just stick up your thumb. Thank you for asking, for now I know. The remaining is the edited phase-of-confusion I waded through.
A Google search shows that the following universities say "finite-state machine":
Quoting Freedman and Ince's "Active Java", p77
An object is something which has a state... the object paradigm is universal.
David J Comer in his book "Digital Logic and State Machine Design" says
...the practical meaning of the existence of states [is a ] set of values measured at various points in a circuit. p.240
(Italics and bolding are mine.) That's one state containing several measurements. And he says:
...it may run through a different sequence of states before returning to the starting state, the system has a finite number of such paths and repetition in inevitable. (p.242)
Obviously finite refers to paths and the three states.
For now, guess what? I make a redirect page to this one, and keep the title. Cpiral Cpiral 05:31, 30 December 2009 (UTC)
Rewrote the intro. Need 2nd opinion for removal of the following tag { { tooshort } } . M!uqomzXb ( talk) 12:03, 4 June 2010 (UTC)
It seems to me that the definition of an "Acceptor" or "recognizer" falls under the definition of a transducer. Why are these written as two different types.. I thought Mealy and Moore machines were the two different types of state machines - as all state machines fall under either one of those categories. Fresheneesz 04:23, 13 December 2006 (UTC)
The section on optimization could really use some further explination! It is practically useless as it stands now. Meekohi 01:52, 30 August 2006 (UTC)
Optimization algorithms for finite state machines are complex and interesting. They should probably have their own pages. Markminn07 ( talk) 04:46, 29 August 2008 (UTC)
State machine is the device readily implemented in a vast number of techniques. THIS IS NOT A MODEL! This is a "tangible" device. This is implementation of a model, not the model itself. Model is always missing some details, while state machine is absolutely concrete, no matter in what way you implement it, in C++ or in VHDL (I did both plenty times). State machine exists as a digital electronics device, the same way as trigger or register; I hope nobody here will say a register or trigger is A MODEL!!! State machines exist in form of software components. Who will say the working software is a model??? Oh my... Neonil ( talk) 14:14, 8 July 2009 (UTC)
I am sorry, but FSM is a model. A register is not a model, obviously, as well it is not a FSM. A register can be modeled in form of FSM. A FSM (that models a register) does not deal with the delays, voltage, mass, material, size, color of the register. More over FSM does not describe full behavior of the device it models (e.g. FSM can not describe the multivibrator circuit on triggers). So, I am sorry I must disappoint you, FSM is a model. (Vladimir E. Zyubin, PhD in CS) Zyubin ( talk) 13:56, 20 November 2011 (UTC)
Was it Alan Turing who invented the concept of a finite state machine by creating the example we now call Turing machines in his famous paper about the decision problem? Jfgrcar ( talk) 04:02, 18 February 2010 (UTC)
hey there! Why is the language link for turkish ends with http://tr.wikipedia.org/wiki/Sonlu_durum_makinas%C4%B1 weird characters? thanks. —Preceding unsigned comment added by 95.90.78.57 ( talk) 16:16, 1 March 2011 (UTC)