Finite automaton
Finite Automaton is a simple idealized machine used to recognize patterns within input taken from some character set called an alphabet. The job of a finite automaton is to accept an input depending on whether the pattern defined by the finite automaton occurs in the input.
       A finite automaton (an abstraction of a computer) is a finite representation of a formal language that may be an infinite set. (Automata is plural, singular is automaton) A finite automaton is a model of a particularly simple computing device that acts as a language acceptor.
Finite automaton, also known as Finite State Machine (FSM) is a mathematical model of computing used in the design of computer programs and sequential logic circuits. They are not actual machines, but abstract machines that may be in any one of some limited number of states at one time.
Formal Definition
Finite automaton (M) is formally defined by the quintuple M = (Q, ∑, δ, q0, F)
Where,
- Q is finite set called States.
- ∑ is finite set called the alphabet.
- δ : Q × ∑ = Q is the transition function.
- q0 is the start state or initial state and
F ⊆ Q the set of final states or accept states.
Example:
Example:Â Here is an example of finite automaton M1
We can describe finite automaton M1 5 tuples ( Q, ∑, δ, q0 and F)
Where,
Q = {Q0, Q1}
∑= {0,1}
δ : Q × ∑ = Q is described with transition table.
State | 0 | 1 |
q0 | q0 | q1 |
q1 | q2 | q0 |
q2 | q1 | q2 |
q0= q0
F= {q1}
A Transition function takes as an argument a state and an input symbol and returns a state. The transition function will be denoted by δ.
         If q is a state and ‘a’ is an input symbol then δ(q0,a) is the state p such that there is an arc labeled ‘a’ from q to p.
For above Finite Automaton:
δ(q0,0) -> q0,
δ(q0,1) -> q1,
δ(q1,0) -> q1,
δ(q1,0) -> q0.
Â
Â
