Finite Automata
Finite Automata
- Finite Automaton (FA) is also called as Finite State machine (FSM).
- Finite Automaton has no temporary storage hence it can remember finite information with the help of finite control which contain states and transitions.
Types of Finite Automata
Finite automata is categorized into two types:
1. Finite automata with output: This is of two types Mealy machines and Moore machines.
(a) In a Mealy machine the output is associated with transition (state and input symbol).
(b) In the Moore machine, output is associated with only state.
2. Finite automata without output: This is of two types, deterministic and non-deterministic.
(a) Deterministic Finite Automata (DFA): It is deterministic finite automata. For every input symbol in DFA there is an exactly one transition from any state of finite automata. It accepts the string by halting at a final state and rejects the string by halting at a non-final state.
(b) Non-deterministic Finite Automata (NFA): It is non-deterministic finite automata. For every input symbol in NFA there is zero or more transitions from any state of finite automata. It accepts the string by halting at a final state and rejects the string either by halting at a non-final state or by halting in a dead configuration.
(c) ε-NFA: It is a nondeterministic finite automaton that can include ε transitions. It has the capability of changing the state without reading the input symbol.
Representations of FA
FA = (Q, Σ, δ, q0, F) is a 5-tuple notation
where, Q is set of finite states,
Σ is an input alphabet containing a finite number of input symbols.
δ is a transition function defined over transitions of FA for state and input.
q0 is the initial state or start state of FA, q0 ∈ Q.
F is the set of final states of FA.
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
