Theory of Computation

By
Prof. Sanjay Patidar (Assistant Professor)
Department of Computer Science &
Engineering,
Delhi Technological University ,Delhi
Theory of Computation, By Sanjay Patidar, CSE ,DTU, Delhi
 A presentation on

Regular Languages and Automata

(Automata theory)

Theory of Computation, By Sanjay Patidar, CSE ,DTU, Delhi

Automata theory

• Contents:
 Introduction
 Chomsky Classification of grammar
 Relationship between languages & machines
 Regular Expression
 DFA and NFA
 Design of DFA and NFA
 Design of FA from regular expression
 Closure Properties of Regular language

Theory of Computation,
Automata theory

• Introduction:
The theory of computation is the subject that
deals with language processes.
Compiler is a language acceptor and translator.

Language :Language is a set of strings or set of

sentences.
Grammar: A grammar is set of rules . With the
help of grammar we can generate the
languages.

01
Theory of Computation,
Automata theory

• Definition:
A grammar G is defined as a quadruple.
G= (V, T, S, P)
Where
V= Finite set of variables (non-terminal)
T= Finite set of terminal symbol
S=S is the start variable
P= Set of productions.

02
Theory of Computation,
Automata theory

• Example 1:
S  AB
A  aA/a
B  bB/b
 It is also known as production rule of the

grammar.
 Terminal symbols are the part of strings

 Non –terminal helps to generate the strings.

 S is a special non-terminal which

representing starting symbol of a grammar.

03
Theory of Computation,
Automata theory

• Language generated by previous grammar.

G= (V, T, S, P)
V= {S, A, B} , T= {a, b} , S= S ,
P= {S  AB, A  aA/a, B  bB/b}
• Sentential forms
S  AB  aB  ab
S  AB  aAB  aaB  aab
S  AB  ab  abB  abb
S  AB  aAB  aaB  aabB  aabb

04
Theory of Computation,
Automata theory

• So the language generated by grammar is:

L= { anbm :n,m >0}
 Any no. of a’s is followed by any no. of b’s.

 At least one a and one b must be present.

• Example 2:
S  aSb/ λ
L= { λ ,ab ,aabb , aaabbb ……. anbn }
L= { anbn :n >0}
 Equal no. of a’s and b’s.

05
Theory of Computation,
Automata theory

• Chomsky Classification of grammar:

Depending on production rule Chomsky
Classified
the grammar into 4 categories

 Type ‘0’ or unrestricted grammar

 Type ‘1 ‘ or context sensitive grammar
 Type ‘2’ Or context free grammar
 Type ‘3’ or Regular Grammar

06
Theory of Computation,
Automata theory

• Type ‘0’ or unrestricted grammar:

Production Rule is of type
 , Where
 ,  are set of terminal and non-terminal

(Variables) i. e (v U t )*
 There is no restriction on , and 

 Example:

aA Bb ,
AaAb

07
Theory of Computation,
Automata theory

• Type ‘1’ or context sensitive grammar :

Production Rule is of type
 , Where
 Where I  I  I  I and  ,   (V T )*
 ,  are set of terminal and non-terminal

(Variables) i. e (v U t )*
 Left hand side should contain at least one

non-terminal.
 Example:

aA Bb ,
AaAb (not allowed)

08
Theory of Computation,
Automata theory

• Type ‘2’ or context free grammar :

Production rule is of type
 , where
 Left hand side or  must be a single non-terminal

only.
  are set of terminal and non-terminal

(Variables) i. e (v U t )*

Example:
AAaB ,
AaB (not allowed)

09
Theory of Computation, NTUEE
Automata theory

• Type ‘3 ‘ or Regular Grammar:

In this the production rule is of type
 Where
=single non-terminal
= a terminal or a terminal Followed by a
non – terminal
 Right hand side should be of form

A a
AaB or ABa
Aaa
 There is restriction on both side of
production. 10
Theory of Computation,
Automata theory

• So, according to Chomsky Classification of

grammar:
Type 3  Type 2  Type 1  Type 0

• Different types Of Languages with their

grammar
 Regular Language – Type 3 grammar

 Context free Language – Type 2 grammar

 Context Sensitive Language – Type 1 grammar

 Unrestricted Language – Type 0 grammar


Recursive

Recursively Enumerable
11
Theory of Computation,
Automata theory

• Relationship between languages & machines:

Arrangement of machines according to decreasing

order of
their power.

TM >LBA>PDA>DFA
12
Theory of Computation,
Automata theory

• Regular Expression
For representation of Regular grammar and
regular languages we use regular expression

a* = {λ ,a , aa,aaa….. } where * =
{ 0,1,2….infinite}

a+ = {a , aa,aaa……...} where + =
{ 1,2…….infinite}
  is a regular expression which represent
empty set. Or null set.
={ }
 (a+ b) or (aUb)= {a,b} or either a or b.
 (a+ b) (a+ b): L= {aa, ab, ba, bb}.
13
Theory of Computation,
Automata theory

• Regular Expression
 (a+b)*

L= {λ ,a , ab, ba…..}
Represent all strings of a and b.
 (a*b*)

L= {λ ,ab , abb, aab…..}

Represent any number of a’s and b’s and a’s
followed by b’s.
 (a*b*)=(b*a*) { Not equal }

 (a*b*)*=(b*a*)*= (a+b)* { Equal }

14
Theory of Computation,
Automata theory

• Regular Expression
 Example1 :

Is L1= an is regular or not?

Sol: an =a*
Counting is not possible but equivalent
regular expression is possible ,So it is regular.
 Example2 :

L2= an bn
 No regular expression possible.

 If it is possible to draw an FA for that

language then that language will be regular.

15
Theory of Computation,
Automata theory

• Condition for Language to be regular

A language is said to be regular if it satisfy at
least one property given below:

 If It is possible to write a regular expression

for the language.
 If It is generated by a regular grammar.
 If It is possible to design FA for the
language.

16
Theory of Computation,
Automata theory

• Automata
 An automata contains a finite set of states. At

each instance in time of some run, automaton is in

one of its states.

 Once the input word has been read, the automata

is said to have been stopped and the state at
which automaton has stopped is called final state.

 The set of all the words accepted by an automata

is called the language recognized by the
automata.

17
Theory of Computation,
Automata theory

• Finite Automata (FA):

Finite Automata is a language acceptor which
accepts regular language.
There are two types of Finite Automata.

 DFA (Deterministic Finite Automata )

 NFA (Non-deterministic Finite Automata )
Both are equivalent in power.

18
Theory of Computation,
Automata theory

• Deterministic Finite Automaton (DFA) :

DFA is a set of state in which there exists a
initial state and one or more than one final state.
A DFA is defined by quintuple.
M= (Q, , , q0, F )
Where
Q= Finite set of internal states
= Finite set of input alpha bat
= Transition Function of type: Q x   Q
q0= Initial state
F= Set of final states and it is subset of Q.

19
Theory of Computation,
Automata theory

• Deterministic Finite Automaton (DFA) :

 For each input alphabet, there is exactly one

transition at every state for every input in DFA.

 Each move of the DFA consumes only one

input alphabet.
 When the end of the string is reached, the

string is accepted. Otherwise the string is

rejected.
 The DFA whose initial state is final state than

it accepts  i.e. null string.

 There also exists a state known as trap state

which has self loop of all the alphabets.

 There is no null transition in DFA.

20
Theory of Computation,
Automata theory

• Design of Deterministic Finite Automaton (DFA) :

Example:1
Design DFA for language in which all strings starts
with “aa” over alphabets {a, b}.
Sol:

21
Theory of Computation,
Automata theory

• Design of Deterministic Finite Automaton (DFA)

:
Example:2
Design a DFA For the language which contains
any number of b’s and exactly 2 a’s.
Sol:

22
Theory of Computation,
Automata theory

• Design of Deterministic Finite Automaton (DFA)

:
Example:3
Design a DFA which accepts even number of
a’s and even number of b’s.
Sol:

23
Theory of Computation,
Automata theory

• Design of Deterministic Finite Automaton (DFA)

:
Example:4
Design a DFA for na (w) mod 3  0
Sol:

24
Theory of Computation,
Automata theory

• Design of Deterministic Finite Automaton (DFA)

:
Example:5
Design a DFA for the language in which
number of a & b are divisible by 3
Sol:

25
Theory of Computation, NTUEE
Automata theory

• Nondeterministic Finite Automaton (NFA) :

 NFA is a finite state machine where for each

pair of state and input symbol there may be

several possible next states.
 This distinguishes it from the deterministic

finite automaton (DFA), where the next

possible state is uniquely determined.
 It may be shown in the formal theory that they

are equivalent, in that, for any given NFA, one

may construct an equivalent DFA, and vice-
versa.

26
Theory of Computation,
Automata theory

• Nondeterministic Finite Automaton (NFA) :

Definition: An NFA is defined by quintuple.
M= (Q, , , q0, F )
Where
Q= set of internal states
= Finite set of input alpha bat
= Transition Function of type: Q x ( U )
 2Q
q0= Initial state
F= Set of final states and it is subset of Q.

27
Theory of Computation,
Automata theory

• Design of Nondeterministic Finite Automaton

(NFA) :
Ex.1
Design an NFA for the language in which any
number of b is followed by ab.
Sol:

28
Theory of Computation,
Automata theory

• Design of Nondeterministic Finite Automaton

(NFA) :
Example:2 Design an NFA for the language that
contains any number of a’s and exactly 2 b’s.
Sol:

29
Theory of Computation,
Automata theory

• Design of Nondeterministic Finite Automaton

(NFA) :
Example:3 Design an NFA for at most 2 a’s and
any no. of b’s.
Sol:

30
Theory of Computation,
Automata theory

• DFA Vs NFA
All the properties of NFA are same as that of DFA
except

 In DFA for each input alpha bat there is exactly

one transition at every state, while in NFA
there may be one or more transition for each
alphabet at any state.
 NFA allows  transition. For Every NFA there
exists a DFA which accepts the same language.
 DFA and NFA are equivalent in power.

31
Theory of Computation,
Automata theory

• Design of FA from Regular Expression

Example: 1 Design an FA for the regular
expression
(a* b)*
Sol:

32
Theory of Computation,
Automata theory

• Design of FA from Regular Expression

Example: 2 Design an FA for the regular
expression a* b*
Sol:

33
Theory of Computation, NTUEE
Automata theory

• Closure Properties of Regular language

 Union:

Let L1= a*b* and L2= b*a* then

L1UL2= a*b* + b*a*
So regular language are closed under union.

 Intersection
L1∩L2= a* + b*
So regular language are closed under
intersection.

34
Theory of Computation,
Automata theory

• Closure Properties of Regular language

 Concatenation:

Let L1= { ab, bab } and L2= { bb,ba } then

L1.L2 = { abbb, abba, babbb, babba}
So regular language are closed under it.

 Complement
L=(a + b)* then L’= 
L=  , then L’=(a + b)*
So regular language are closed under
complement.

35
Theory of Computation,
Automata theory

Reg

 (0 3 ) * 00  { 0 n | n mod 3  2 }

 { a n b n | n  0} C
F
CS l
a b
 L  {an bn cn | n  0 } i d l e
e c ab
D er
m
 algorithm to answer " x  L ?" eEnu
b ly le
ta b
pu m er a
 LH Co
Halting Problem
m
Enu
b l y
u t a
 LH omp
n -C
No 36
Theory of Computation,
Automata theory

Thanks

37
Theory of Computation,