Finite State Machine

Finite State Machine

A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but it rests on the given input symbol. The automata have two-state; either they advance to the next state or stick in the same state. The accepted state of automata is when it reaches the final state, and the input symbol is successfully processed.

Finite automata consist of the following:

Q: Finite set of state

?: Finite set of an input symbol

q0: Initial state

F: Final state

?: Transition function

The transition function can be defined as:

?: Q x ??Q

The construction of finite automata

Let consider L(r) is a regular language, and it is recognized by some finite automata(FA)

• State– It is represented by circles. The state's names are written inside the circles.
• Start state– Thestarting point of automata is termed as a start state. This state has an arrow coming towards it.
• Intermediate state– The states with at least two arrows, one is pointing towards them and another pointing out from them.
• Final state– The final state is depicted by a double circle. Any input string is successfully parsed, then the automata will be expected to be in the final state. The final state may have any odd number of arrows pointing towards them and even numbers of arrows pointing out from them. But the number of the odd arrow will be one greater than the even arrow, i.e., odd = even + 1.
• Transition– It is the collection of circles or nodes, called state. Each state depicts a condition that could happen during the process of scanning the input. Edges are pointed from one state of transition to another. Each edge is marked by a symbol or set of the symbol.

Finite automata come in two ways:

• DFA(Determinist finite automata)
• NDFA(Non deterministic finite automata)

DFA

It stands for deterministic finite automata. For each state 'a' and input symbol b, there is exactly one edge out of a labeled b. A finite automaton is said to deterministic for an input symbol if there exists a unique resultant state. It means for each input; there is only one transition. It represents the uniqueness of computation. It doesn't accept a null value.

DFA has five tuples {Q, ?, q0, F, ?}

Q- Set of all states
?- Finite set of input symbol where ?: Q x ? ?Q
q0- Initial state
F- Final state
?- Transition function

Example

Q = (q0, q1, q2)

? = (0, 1)

q0 = (q0)

F = (q3)

NFA
It stands for non-deterministic finite automata. It does not have any limit on the label of their edges. A finite automaton is said to be non-deterministic: If we have more than one transition state for a single input, then the non-deterministic finite automata accept the null move.

Non-deterministic finite automata consist same five tuples as deterministic finite automata. The only difference is the transition function that is mentioned below:

Transition function:

                           ?: Q x ? ?2Q

We can represent deterministic finite automata (DFA) and non-deterministic fine automata (NFA) by transition graph, where the nodes are state and labeled edges represent the transition function.

Example

Q = (q0, q1, q2)

? = (0, 1)

q0 = (q0)

F = (q3)

Difference between DFA and NFA

S.N	DFA	NFA
1	DFA stands for Deterministic Finite Automata.	NFA stands for Non-deterministic Finite Automata.
2	In DFA, for each pair of state and symbol, the next possible state is unique.	In NFA, each pair of state and symbol can have more than one next state.
3	DFA cannot use an empty string.	NFA can use a null string.
4	It is difficult to construct	It is easier to construct
5	Backtracking is may or may not allow	Backtracking is allowed
6	It requires more space.	It requires less space.

7	EF can be understood as one machine.	NFA can be understood as several little machines.
8	All DFA is NFA.	Not all NFA is DFA.

9

Execution time is less.

Execution time is more.