I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?
$\begingroup$
$\endgroup$
9
-
6$\begingroup$ From Wikipedia: "... In automata theory, a branch of theoretical computer science, a deterministic finite automaton (DFA) — also known as deterministic finite state machine — is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string ...". DFA is the preferred term used in automata theory, FSM is the preferred term used in practical applications. $\endgroup$– VorMar 7, 2013 at 11:05
-
4$\begingroup$ I think FSM is more inclusive, including also Mealy and Moore automata. NFA are one specific model. $\endgroup$– RaphaelMar 7, 2013 at 11:26
-
$\begingroup$ @Raphael: I agree with you , FSM seem broader (even wikipedia makes the distinction between Transducers, Acceptors, Classifiers and Sequencers). "DFA"~"FSM acceptors" (FSM with only yes/no output) ... furthermore FSM in circuit designs, usually make use of outputs ... Perhaps you can convert your comment to an answer. $\endgroup$– VorMar 7, 2013 at 13:01
-
$\begingroup$ Personally, I use FSM as a broad term that includes DFA, NFA, Mealy and Moore machines, (finite-state) transducers etc; simply everything with a finite state space and without auxiliary memory. $\endgroup$– DanMar 7, 2013 at 15:34
-
1$\begingroup$ @Raphael In in formal-theory (or theory of computation) we prefer to use word "Automata" -- to emphasis that our machine is 'automatic' machine (self moving- like your computer) - "automatic" in the sense that once you have been defined transition rules, you do not need to apply any explicit intelligent to process/classify strings (you just need to refer transition rules at each step). -- whereas machine term is prefered in context of device (rather than model) -- though both are synonyms of each other. $\endgroup$– Grijesh ChauhanMar 25, 2014 at 15:32
|
Show 4 more comments
4 Answers
$\begingroup$
$\endgroup$
1
As far as I understand, both have "states", and "actions" that make the machine move from one state to another upon an input signal. Thus the conceptual ideas are the same. There is some difference in the details.
In FSM for circuit designs the input signal is mostly assumed to be a bit (binary), whereas in finite state automata one can have a general "abstract" alphabet of input symbols. Second, a FSM also generates an output, associated to the state reached, also binary. In automata terminology this 'extension' is called a Moore machine. Automata however have final (or accepting) states, that signal a favourable input read. Finally, FSM are mostly deterministic, i.e., for each input in a certain state there is one next state. In automata theory one also considers the nondeterministic variant where one might have choice in where to move.
answered Mar 7, 2013 at 15:37
-
$\begingroup$ Readers may also refer to stackoverflow.com/a/22425038/1029599 $\endgroup$– KGhatakFeb 18, 2022 at 8:36
$\begingroup$
$\endgroup$
Based on my experience as well as the Wikipedia article, there are several kinds of finite state machines, including
Some of the notions flying around differ mostly in motivation; some arose from language and/or computability theory, others from computer architecture.
Note that you can also change several paradigms to get automata that are, arguably, still finite-state automata, for instance
As you can see, vanilla finite automata as taught in TCS 101 is but one flavor of many, each with their own (more or less formal) definition.
$\begingroup$
$\endgroup$
Although the main idea on which they both rely on is same. Both use finite states and jump to another state as the input feed. However, FSM being a machine, like Full adder or SR flipflop has bits as input and output. Yeah, FSA also has bit output, 0 for non terminating state and 1 for terminating state, but it is an abstract mechanism and not seen. There is difference in the digraphs that is drawn to represent them. Beside that FSA is a logical and computation device while FSM is a digital logic device.
$\begingroup$
$\endgroup$
Based on the book, Introduction to Languages and the Theory of Computation , they are interchangeable terms.
... These are examples of a type of language acceptor called a finite automaton (FA), or finite-state machine.
