Finite Automaton
A Finite State Machine (FSM) or finite state automaton is an abstract machine used in the study of computation and language that has only a finite, constant amount of memory.
Description of Finite Automaton
This finite automaton is also known as Deterministic Finite Automaton (DFA). But when the transition function maps Q x Ʃ → 2Q, (2Q is called Powerset function, is used then that automaton is known as Non- Deterministic Finite Automaton (NDFA or NFA).
A finite automaton is defined as 5-tuples (Q, Ʃ, δ, q0 , F)
Where, Q is finite non-empty set of states.
Ʃ is finite non-empty set of input symbols.
δ is transition function which maps Q x Ʃ into Q.
q0 is initial state and q0 ϵ Q.
F is set of final states and f intersection Q.
Transition Diagrams
A transition diagram is a finite directed labeled graph in which each vertex represented a state and directed edges indicate the transition from one state to another. Edges are labelled with input/output. In this, the initial state is represented by a circle with an arrow towards it, the final state is represented by two concentric circles and intermediate states are represented by just a circle.
e.g., In the given transition diagram, vertex A is the initial state of the finite automata and vertices A and B are the final states and all the edges of this transition diagram are labelled with the inputs.
Transition Table
Transition table is the tabular representation of transition system. In this representation, initial (start) state is represented by an arrow towards its and a final state is represented by a circle.
In this transition table, we have mentioned only three states q0 , q1 and q2 , q3 is not mentioned because q3 state is not reachable to any other node.
Key Points
- Transition function is usually represented by a transition table or a transition diagram.
- Finite automata are finite collections of states with transition rules that take input to move from on state to another.
- The machine starts in the start state (initial state) and reads in a string of symbols from its alphabet. It uses the transition function δ to determine the next state using the current state and the symbol just read. If, when it has finished reading, it is in an accepting states, it is said to accept the string, otherwise it is said to reject the string.
Acceptability of a String by Finite Automata
A string ω is accepted by a finite automaton, M= (Q, Ʃ, δ, q0 , F), if , δ (q0 , ω) =F, where q0 is initial (start) state and F is the final state.
Note FA (Finite Automata) must accepts those strings which are in the given language but should not accept those strings which are not in the language of finite automata.
Transition Function It takes two arguments i.e. , a state and an input symbol. , δ (q, a) is the transition function for the DFA (Deterministic Finite Automata) which is at state q and when it receives the input a, DFA will move to the next state.
Extended Transition Function It takes two arguments a state and an input string
δ* (q, ω) = δ(δ(q, x),a)
where, ω is a string i.e., ω= xa, in which a is a single word and x is remaining string except the last symbol.
Key Points
- The finite automata has only string pattern recognising power.
- Generally, all FA having only one reading head on the input tape, but a FA having more than one reading head has equal power as FA with one reading head.
- A language Lϵ E* is regular if and only if there is a FA that recognizes L.
Language of a DFA
An automata of all kinds defined language. If A is an automata, L(A) is its language.
For a DFA A, L(A) is the set of string labelling paths from the start state to a final state. Formally, L(A) is the set of strings ω such that δ(q0, ω) is in F (final state or set of final states).
e.g. , String 101 is in the language of the DFA below. Start at A. Follow arc labelled 1, then arc labelled 0 from current state B, finally, arc labelled 1 current state A. Result in an accepting state, so 101 is in the language.
The language of our example DFA is:
L = { ω | ω is in {0,1}* and ω does not have two consecutive 1’s}
- Read a set former as the set of strings ω such that these conditions about ω are true.
Equivalence of DFA and NDFA
In constrast to the NFA (NDFA), the Deterministic Finite Automata (DFA) has
- No ^-transition (null transition).
- For every (q, a) with q ϵ Q and a ϵ Ʃ at most one successor state.
- A Deterministic finite automata can simulate the behavior of NFA by increasing the number of states.
Key Points
- In Deterministic Finite Automata (DFA), for each state, there is at most one transition for each possible input.
- In non- deterministic finite automata, there can be more than one transition from a given state for a given possible input.
- If a language L is accepted by an NFA, then there is a DFA that accepts L.
- All DFA are NDFA, but not all NDFA are DFA.
- All NDFA are DFA have the same power.
- Processing of an input string is more time consuming when NFA is used and less time consuming when DFA is used.
Finite Automata having ^- moves
The model NFA include those transitions by which, without giving any input FA can move to the next state.
Finite Automata With Output Capabilities
The finite automata was explained in above sections have binary output i.e. , either they accept the string or they do not accept the string.
Under finite automata, there are two other machines
Moore Machine
It is a finite automata in which output is associated with each state. Each state of Moore Machine has a fix output.
Moore Machine is defined as 6-tuples (Q, Ʃ, Δ, δ, λ, q0)
Where, Q is finite non-empty set of states.
Ʃ is set of input symbols.
Δ is output alphabet.
δ is transition function which maps δ(Ʃ x Q) → Q.
q0 is initial state.
λ is output function which maps Q into Δ.
Mealy Machine
It is a finite automata in which the output depends upon the present input and present state, both.
Mealy Machine is also a 6-tuples (Q, Ʃ, Δ, δ, λ, q0), Where all symbols except λ have the same meaning as in Moore machine. λ is the output function mapping Ʃ x Q into Δ.
Key Points
- We can construct equivalent Mealy machine for a Moore machine and vice-versa.
- If M1 and M2 respectively, for input string ω. Then, the length of T1(ω) is one greater than the length of T2(ω) i.e. ,
|T1(ω)|= |T1(ω)| +1