CLASS 2 : FINITE AUTOMATA (FA)

AUTOMATA : 

Automata stands for automatic machine. A machine which operate automatically is called automatic machine.

MACHINE : 

Machine is a device which receive input and produce output.

Machine are characterise in two types:

1. Physical machine.
2. Logical machine.

1. PHYSICAL MACHINE:  

Physical machines like Fan, Washing machine, Refrigerator etc. Here we do not study about physical machine.

2. LOGICAL MACHINE: 

Logical machines are those which have logical existence. like Programs, Flowcharts, DFD's etc.

Logical machine is further characteristics into two parts such as:

 a. Machine with output.
 b. Machine without output.

a. MACHINE WITH OUTPUT : 

It is normal machine because every machine gives output.

b. MACHINE WITHOUT OUTPUT:  

Machine without output means machine only checks the validity of input that mean weather input is valid or not. (It generates only decision). Input are in the form of words or token.

INFORMAL DEFINITION OF F.A:

Informal means those definition which is define informally (means itself without any rules and regulations).

Finite Automata is an automatic machine which take input, process it and possibly generate output and have countable number of states.


FORMAL DEFINITION OF F.A:

Formal definitions are those definition which are define in terms of sets, equations and symbols.

Finite Automata is a set of five tupples or elements.

F.A = ( Q , Σ ,  δ ,  q₀  , F )

where :  Q  is a set of states
              Σ (Sigma)  is a set of Input symbols

              δ (Delta)   is a transition function / mapping

              q₀  is a Initial state
              F   is a set of final states.
Note: Initial state (q₀) will be only one or (unique) and Final state will be more then one. Example a fan have 3 states such as (rest, motion, termination)


      δ :  Q X   Σ → θ