Finite state automata

KASHIRAM POKHAREL
HCOE
Automata
• It is abstract models of machine that performs computations on an
input by moving through a series of state or configuration
• Different type of automata are
• Finite state automata
• Pushdown automata
• Linear bounded automata
• Turing machine.
 Finite state machine
• Finite state machine is an abstract model of a machine with a primitive
internal memory.
• A finite state machine is defined as a system where energy, materials and
information are transformed, transmitted and used for performing some
functions without direct participation of man.
• E.g. automatic machine tools, automatic packing machines etc. The block
diagram of FSM can be shown below
Characteristics of FSM
Input:
• At each of the discrete instant of time t1, t2,……. tn, input values I1, I2 ……, In
each of which can take a finite no. of fixed values from the input alphabet Σ.
Output:
• O1, O2- - - - - On are the outputs of the model, each of which contain finite no
of fixed values from an output.
States:
• At any instant of time the automatic can be in one of the state q1, q2 ….qn.
State Relation :
• The next state of an automatic at any6 intent of time is determined by the
present states and the present input.
Output Relation :
• Output is related to either state only or to both the input and the state.
• A finite state machine (FSM) is mathematically defined by
M={Q , Σ , O , δ , S0 ,G}
Where,
Q = finite non empty set of states,
Σ = finite non empty set of inputs symbol called input alphabets.
O = finite set of output symbol
δ = transition function that takes two argument as state, input and
returns an argument as state.
S0 Є Q is the initial state.
G = output relation that takes two arguments as state input and
returns two argument as output
FSM example: on-off switch
• A finite state machine (FSM) is mathematically defined by
M={Q , Σ , O , δ , S0 ,G}
Where,
Q = {on-off},
Σ = {press}
O= {fan-off , fan-on}
δ = transition function is defined as
{on, press}{fan-off}
{off, press}{fan-on}
q Є Q is the initial state.
F= output relation is defined as
{on, press}{off, fan-off}
{off, press}{ on, fan-on}
FSM :2- bit adder
Carry P Q Sum

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1
Type of FSM
Differentiate between FSM and FSA
FSM FSA
?? ??
• Alphabet:
• An alphabet is a finite, nonempty set of input symbols. The alphabet of a
language is normally denoted by ∑
• example:
binary alphabet is ∑={0,1}
• String:
• Multiple occurrence of input symbol in any order taken from some given
alphabet. It is denoted by w
• A string or word over an alphabet ∑ is a finite sequence of concatenated
symbols of ∑
• 0110, 11, 001 are three strings over the binary alphabet { 0, 1 }
aab, abcb, b, cc are four strings over the alphabet { a, b, c }.
• Language
Collection of all possible string over some given alphabet.
It is denoted by L
Language L over the alphabet (∑ ) is the subset of ∑* . Any set of strings over an
alphabet ∑
i.e. any subset of ∑* will be called a language. Thus ∑* , ø and ∑ are languages.
For ∑= { 0, 1}
L= { x : x є { 0,1 } *| x is any positive number }
011011100 є L ,
1111 є L ,
1011011000 Є L
Finite State Automata:
• A finite state automata is a mathematical model used to determine
whether the string is accepted or rejected.
• Due to this reason it is called language recognizer.
•
 Working principle
• FA always starts from its initial state
• FA takes input from the string one by one symbol from left to right
• Consuming one input symbol finite automata change its state according
to defined transition function and it continues until all symbol are
consumed.
• After all input symbol are consumed by the automata it stops its work.
• If the automata halts at any of the final state then string is accepted
string otherwise non accepted.
Component of FSA
Input tape:
the input tape is divided into squares, each square containing a single symbol from
the input alphabet Σ.
Reading head:
the head examines only one square at a time and can move one square either to
the left or to the right.
Finite control:
the input to the finite control will be usually symbol under the R-head or the
present state of the machine say 'a' to give the following output.
A motion of R-head along the tape to the next square.
The next state of the finite automata is given by
Representation of FA

Analytically, a FA can be represented by a 5 tuple M={Q , Σ , δ , q0 ,F}

where -
• Q is finite non empty set of states,
• Σ is a finite non empty set of inputs called input alphabets.
• δ is a function which maps Q x Σ to Q & is usually called direct transition
function.
• q0 Є Q is the initial state.
• FC Q is the set of final states, also called accepting state.
Notations for FSA or FA:-
• There are two preferred notations for describing automata.
• 1. Transition diagram or graph.
• 2. Transition table
1. Transition diagram or graph.
• A transition graph or transition diagram is a finite labeled graph in which
each vertex represents a state and the directed edges indicate the
transition of a state and the edges are labeled with input.
• The initial state is represented by a circle with an arrow pointing toward
it, the final state by two concentric circles and other states are
represented by just a circle.
• (q1, 0) q0, (q1, 1) q1, (q0, 1)q1, (q0, 0) q0. q0 is initial state
q1, is final state.
Transition table:-
• A transition table is a conventional, tabular representation of a function
like δ that takes two arguments and returns a value. The rows of the
table correspond to the states and the column corresponds to the
inputs. The entry for the row corresponding to the state q and the
columns corresponding to input a is the state δ (q, a).
Q\ Σ 0 1

q0 q0 q1

*(q1) q1 q0
Type of FA

• Deterministic finite automata (DFA)

• Non- Deterministic finite automata (NFA)
 DFA
• DFA is a FA that is in a single state after reading any sequence of inputs. The
term deterministic refers to the fact that on each input there is one and
only one state to which the automata can transition from its current state.
DFA consists of– M={Q , Σ , δ , q0 ,F}
A finite set of states Q.
A finite set of states of inputs symbols Σ.
A transition function that takes as arguments a state and an input symbols
& return a state. The transition function is denoted by δ. If q is a state, and a
is an input symbol then δ (q, a) in that state p such that there is an arc
labeled a from q to p. i.e. δ (q, a)p
A start state, one of the states of Q.
A set of final or accepting states F. The set F is a subset of Q.
• Create a DFA that ends with the substring ab with alphabet{a,b}.
• Create a DFA that accept a language over(a,b)* which always starts with
substring ab
• Create a DFA that accept a language over (a,b)* which contains even
number of a
• Create a DFA that accept a language over (a,b)* which start with a
substring baa
• Create a DFA that accept a language over (a,b)* which contains
• two consecutive a.
• Start with aba
• Ends with abab
• 3 consecutive a
• Doesn’t contain consecutive a
• Even number of b.
• Odd number of a and odd number of b
• Doesn’t contain 3 consecutive b.
 a Q\ Σ a b
A a B b C
A B A
b a
b B B C
*C B A

• FSA that ends with substring ab over alphabet(a,b)*

 Q\Σ 0 1
*q0 q2 q1
q1 q3 q0
String acceptance q2 q0 q3

of DFA q3 q1 q2

So/n: δ(q0, 1 0 1 0 1) = δ (q1,1 0 1 0 1)

= δ(q0, 0 1 0 1)

= δ(q2, 101)

= δ(q3, 0 1)

= δ(q1, 1)

= δ(q0, Є) = q0
NFA
M={Q , Σ , δ , q0 ,F}
A finite set of states Q.
A finite set of states of inputs symbols Σ.
A transition function that takes as arguments a state and an input
symbols & return a state. The transition function is denoted by δ. If q
is a state, and a is an input symbol then δ (q, a) in that state p such
that there is an arc labeled a from q to p. i.e. δ:QxΣ p(Q)
* :Q * -> 2Q
A start state, one of the states of Q.
A set of final or accepting states F. The set F is a subset of Q.
Conversion of NFA to DFA
• For every non-deterministic finite automaton there exist equivalent
deterministic finite automatons.
• Every state of a DFA will be represented by some sub set of a set of states
of NFA and therefore the transition of NFA to DFA is normally called a
subset construction.
steps
Step: 1. Seek all the transitions from start state q0 for every symbol Σ.
If we get a set of states for same input then, consider that set a new
single state.
Step: 2. for new state check all the transition for every symbol in Σ.
Step: 3. Repeat step 2 till we are getting a new state. All those states
which consists at least one accepting state of given NFA will considered
as final states.
Here, the new state is {q0, q1} so we have to check all the transition of
{q0. q1} for every symbol in Σ.
Convert the following NFA to DFA

Q\Σ 0 1

*q0 {q0} {q1}

q1 {q1} {q0,q1}
 δ' ({q0, q1} ,0) = δ (q0, 0) U δ (q1, 0)

= {q0} U {q1}

= {q0, q1} Old state

δ ({q0, q1},1) = δ(q0, 1) U δ (q1, 1)

Q\Σ 0 1

{q0} {q0} {q1} = {q1 } U{q0, q1}

{q1} {q1} {q0, q1}

{q0, q1} {q0, q1} {q0, q1} = {q0, q1} Old state
Differentiate between NFA and DFA

NFA DFA
?? ??
 Regular expression:-
• An expression that generates all the strings for finite automata is called
regular expression
• Regular expressions are useful for representing certain set of string s in an
algebraic manner.
• A regular expression can be recursively defined over Σ as follows
Any terminal symbol (Σ) ,empty string(Є), empty state(Ø) is regular
expression.
If R1 and R2 are regular expression then union of two R.E R1 and R2
written as R1 + R2 is also RE.
The concatenation of two R.E R1 and R2 written as R1.R2 is also R.E.
The iteration (or closure) of a R.E R, written as R* is also a R.E.
If R is R.E, then (R) is also a R.E.
Σ={0,1}
(0+1)*={Є,0,1,00,11,10,01} i.e. Closure of union
(0.1)*={Є,01,0101,010101 … }
0*={Є,0,00,000,0000 ……}
0* +1* = {Є,0,00,000,1,11,111….} i.e union of closure.
11*={1,11,111,…} i.e. at least one 1 followed by any number of 1
L : {all the string over Σ={0,1}, starting with 1 and ending with 0}
1(0+1)*0
Regular expression to finite automata
• Theorem:
Every regular expression R can be recognized by a transition
system i.e. for every string with the set R, there exists a path from
the initial state to a final state with path value w.
Σ={0,1}

0.1 0+1 0*
A 0.1 C A 0+1 C
0

A 0 B 1 C A C

1
(0+1)* (00+11)* (0+1)*

(0+1)* (00+11)* (0+1)*

q0 qf

(00+11)*
(0+1)* (0+1)*
q0 q1 q2 qf
Create a state diagram for the following R.E

• 10+(0+11)0*1
• (ab+c*)*b
• a+bb+bab*a
• (a+a(b+aa)*b)*a(b+aa)*a
Construction of R.E. From DFA:

• Arden's Theorem:
• Let P and Q be two regular expressions over E. If P does not contain Є,
then the following form in R,
R = Q + RP
has a unique solution given by R = QP*
Construct a regular expression corresponding to the
following state diagram.

• Equations: 0 1
q1 = q1.0 + q3 0 + Є --------------(1)
q2 = q1.1 + q2.1 + q3.1 -----------(2) q1 1 q2
q3 = q2.0 ---------------------------(3)
From (2) and (3) we get - 0 1 0
q1 = q1 1 + q2 1 + (q2 0) 1
q3
q1 = q1.0 + q3 0 + Є ----------(1)
q2 = q1.1 + q2.1 + q3.1 ----(2)
q3 = q2.0 ----------------- --(3)
GRAMMAR
• Grammar is defined as the set of rules defined to generate a string.
• grammar consists of one or more variables that represent classes of strings
• (i.e., languages)
• Eg. R.E =a(a*+b*)b
SaMb
MA //it is null production needs to be removed
MB // it is null production needs to be removed
AaA/ Є
BbB/Є
• A grammar is defined as G={v, Σ,R,S}
where
V= finite set of non-terminals
Σ= finite set of terminals
R= finite set of production rules
S=start symbol
Type of grammar
• Regular grammar
• Context free grammar
• Context sensitive grammar
• Unrestricted grammar

Normally the production rule of each grammar is of the

form
String1string2
Unrestricted grammar
• If there is no restriction applied to the production rule of a grammar
then it is said to be unrestricted grammar.
• The equivalent machine for unrestricted grammar is Turing machine.
Context sensitive grammar
• A grammar is said to be context sensitive if its production rele is of
the form
W1αW2  W1βW2 Where,
α,β Є V and
W1,W2 Є Σ
• Example:
aSbcAd
• The equivalent machine for context sensitive grammar is Linearly
bounded automata.
Context free grammar
• If G is a CFG then all production in R has the form –
α→β
Where α ЄV and β Є (Σ UV)*
Example:
A a, A Є A aB A  Bb AABC etc.
• The equivalent machine for context free grammar is pushdown
automata.
Regular Grammar
• A grammar whose production rule is in the form of:
Nonterminal  one terminal
Nonterminal  Є
Nonterminal  <one terminal> <one nonterminal>
Example:
Aa, AaA
All regular grammar are context free but not vice versa.
The equivalent machine for Regular grammar is Finite automata
Derivation:
• The sequence of production rule used to generate a terminal string is
called derivation. Let w1,w2,….wn be the strings. Then the derivation
is defined as:
W1w2W3……………Wn
There are two type of derivation
1. Left most derivation
2. Right most derivation.
• A derivation which always replace the leftmost non-terminal in each step is
called a leftmost derivation or A derivation A W is called left derivation if
we apply a production only to the leftmost variable at every step.
e.g
S → OB|1A,
A → O|OS|1AA,
B → 1|1S|OBB.
W=00110101. Then,
S  OB
 OBB
 001B
 0011S
 0011OB
 001101S
 0011010B
 00110101
• A derivation A W is a rightmost derivation if we apply production to the
rightmost variable at every step.
S  OB
 OBB
 00B1S
 00B1S
 0010B
 00B101S
 00B 1010B
 00B10101
00110101
Derivation tree(Parse tree)
• The in a CFG can be represented using trees. Such trees representing
derivations are called derivative trees or parse trees
• A derivation tree for a CFG G = (V, Σ, S, R) is a tree satisfying the
following conditions.
Every vertex has a label which is a variable of terminal or A
The root has label S.
The label of internal vertex is a variable.
If the vertices n1 n2, ….. nk written with labels x1 x2 …… xk are the
children's of vertex n with
 lab le A,. Then A → x1 x2 …… xk is a production in R
G = ({s, A} ,{a, b} ,R consists of , S→aAS |SS|a , A→Sba | ba.} ) &
w = aabaa

Then S  SS
 aS [S→a]
 aaAS [S→ aAS]
 aabaS [A→ba]
 Aabaa [S→a]
Ambiguity in CFG:

• If there exist more than one leftmost derivation or more than one
rightmost derivation tree for the same string then the grammar is said
to be ambiguous grammar
Check whether the grammar G with production rules −
X → X+X | X*X |X| a
is ambiguous or not.?

• Let’s find out the derivation tree for the string "a+a*a". It has two
leftmost derivations.
X → X+X
→ a +X
→ a+ X*X
→ a+a*X
→ a+a*a
•X X*X
 X+X*X
 a+ X*X
a+a*X
 a+a*a

As there are two parse trees for a single string "a+a*a", the grammar G
is ambiguous.
• Write a CFG for the regular expression r = 0*1(0+1)*
Solution,
• To generate a grammar we divide the regular expression into 3 parts 0*, 1, (0 + 1)*
represented by 3 non-terminal symbols.
Let the CFG be G={V, Σ,R,S}
• Here, V = {S, A, B}
Σ= {0, 1}
And productions R are defined as
S  A1B
A  0A/ϵ
B  0B/1B/ϵ Let us test the grammar against an example : 001011
S => A1B
=> 0A1B
=> 0A1B
=> 00A1B
=> 0010B
=> 00101B
=> 001011
Write a CFG that generates all the signed integers

• Number<sign> <integer> G={V, Σ,R,S}

• Sign+/- Where,
• Integerdigit/digit integer V={ }
• Digit0/1/2/3/4/5/6/7/8/9 Σ={ }
• Example for -376 R={ }
• Number<sign> <integer> S= { }
- <integer>
- digit <integer>
- 3 <integer>
- 3 digit <integer>
-3 7 <digit>
-3 7 6
Write a CGF that generate the following sentences
A hungry rabbit eats quickly
Sentences<noun phrase> <verb phrase>
Noun phrase <article><noun>
Article  a/an/the
Verb phrase  verb/adverb/adjective
Verb  eats
Adverb  quickly
Adjective  hungry
Noun  rabbit
Construct a FA using grammar:
• We define M as {{q0,q1,…..qn.qf},∑ ,∂ ,q0,{qf}} where ∂ is transition
function.
• Each production AiaAj induces a transition from qi to qj with level a
• Each production Aja induces a transition from qk to qf with level a
 Let M={{ q0,q1 qf },{a,b},∂, q0, A0}
• Let G={{A0,A1},{a,b},p,A0}where Where q0 and q1 Correspond to A0 and A1
P consists of respectively and qf is the new(final) state
introduced.
• A0aA1
Now,
• A1bA1 A0aA1
• A1a Induce a transition from q0 to q1 with level a
• A1bA0 A1bA1
• Construct a transition system M Induce a transition from q1 to q1 with level b
accepting L(G) A1a
Induce a transition from q0 to qf with level a
a
a A1bA0
q0 q1 qf
Induce a transition from q1 to q0 with level b
b b
 THANK YOU