Finite Automata
Types of Finite Automata |
There are two types of Finite Automata:
- FA without output
- FA with output
FSM or FA without output: An automaton in which only a state is also obtained as output on scanning the input string. The two main types of FSMs in this category are Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA).
Deterministic Finite Automaton (DFA): A DFA is a type of automaton where each input symbol causes the machine to transition to a single next state. The transition is determined by the current state and the input symbol. DFAs are used for tasks like pattern matching and string recognition.
Non-deterministic Finite Automaton (NFA): An NFA is an automaton where multiple transitions can occur from a single state for a given input symbol. This non-determinism provides more flexibility but requires additional mechanisms for decision-making during transitions.
FSM or FA with output: An automaton in which the output is also obtained on input, for example, Mealy and Moore machines.
- Moore machine: the automaton in which the output depends only on the present states of the machine.
- Mealy machine: the automaton in which the output depends on the present states and input at any instance of time.
In summary, the distinction between FSM or FA with output and FSM or FA without output lies in whether the automaton produces output during transitions. Moore and Mealy machines fall under the category of FSM with output, while DFA and NFA fall under the category of FSM without output. Each type has its own applications and use cases in modeling and solving various computational problems.
Theory of Computation Notes
आशा करता हूँ, कि यह आर्टिकल आपको पसंद आया होगा तो सोच क्या रहे हैं अभी इसी वक्त इसे अपने दोस्तों के साथ सोशल मीडिया पर Share करें।
Thanking You………………धन्यवाद………………..शुक्रिया………………..मेहरबानी…………………..