Finitne Automata Introduction || Formal Languages Automa Theory

Finite Automata(FA) is the simplest machine to recognize patterns.

A Finite Automata consists of the following :

Q : Finite set of states.

∑ : set of Input Symbols.

q : Initial state.

F : set of Final States.

δ : Transition Function.

Formal specification of machine is  { Q, ∑, q, F, δ }.

FA is characterized into two types:  DFA and NFA

Transition

The following are the two equivalent definitions for the transitions of a finite state system.

a.   Transition is the act of passing from one state/place to the next.

b.   A change from one place or state or subject or stage, to another.

Transitions are represented in the following ways:

§  State diagram or transition diagram.

§  State transition table.

§  Transition function.

A diagram consisting of circles to represent state and direct line segment to represent transitions between the states, is called the state diagram. The symbols used in the diagrams are enlisted in table below.

Example (state diagram):

A.   S1 and S2 are state and S1 is an accept state. Each edge is labelled with the input.

State transition table:

A state transition table can be described, in general, as:

§  Tabular representation of transition that take two arguments and return a value.

§  Rows corresponding to state and columns corresponding to inputs,

§  Entries correspond to next state.

§  The start state is marked with an arrow (à).

§  The accepting states are marked with star, (*).

Inputs States	Parent inputs
	a1	a2	…	an
S0
S1
…
Sn

Table   State Transition Table Format