Unit 2 – Regular Languages & Finite Automata

1. Regular language & Regular Expression.

Regular Language :-
A Regular Language over an alphabet ∑ is one that can be obtained from this basic language using
the operation of Union, Concatenation and Kleene (*).
Regular Expression :-
 Regular Language can be described by an explicit formula.
 It is common to simplify the formula slightly by leaving out the set brackets {} or replacing
them with parenthesis () and replace U by +. The result is called Regular Expression.
Language Regular Expression
1. {^} ^
2. {0} 0
3. {001} 001
4. {0,1} 0+1
5. {0,10} 0+10
6. {1,0}110 (1+0)110
7. {110}*{0,1} (110)*(0+1)
8. {1}*{10} (1)*(10)
9. {10,111,11010}* (10+111+11010)*
10. {0,10}*({11}*U{001,^}) (0+10)*((11)*+(001+^))
Table 2.1. Regular Expression
More Examples of regular Expression
1. 0 or 1
0+1
2. 0 or 11 or 111
0+11+111
3. Regular expression over ∑={a,b,c} that represent all string of length 3.
(a+b+c)(a+b+c)(a+b+c)
4. String having zero or more a.
a*
5. String having one or more a.
a+
6. All binary string.
(0+1)*
7. 0 or more occurrence of either a or b or both
(a+b)*
8. 1 or more occurrence of either a or b or both
(a+b)+
9. Binary no. ends with 0
(0+1)*0
10. Binary no. ends with 1
(0+1)*1
11. Binary no. starts and ends with 1.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 1

 Unit 2 – Regular Languages & Finite Automata

1(0+1)*1
12. String starts and ends with same character.
0(0+1)*0 or a(a+b)*a
1(0+1)*1 b(a+b)*b
13. All string of a and b starting with a
a(a/b)*
14. String of 0 and 1 ends with 00.
(0+1)*00
15. String ends with abb.
(a+b)*abb
16. String starts with 1 and ends with 0.
1(0+1)*0
17. All binary string with at least 3 characters and 3rd character should be zero.
(0+1)(0+1)0(0+1)*
18. Language which consist of exactly two b’s over the set ∑={a,b}
a*ba*ba*
19. ∑={a,b} such that 3rd character from right end of the string is always a.
(a+b)*a(a+b)(a+b)
20. Any no. of a followed by any no. of b followed by any no. of c.
a*b*c*
21. String should contain at least 3 one.
(0+1)*1(0+1)*1(0+1)*1(0+1)*
22. String should contain exactly two 1’s
0*10*10*
23. Length of string should be at least 1 and at most 3.
(0+1) + (0+1) (0+1) + (0+1) (0+1) (0+1)
24. No.of zero should be multiple of 3
(1*01*01*01*)*
25. ∑={a,b,c} where a should be multiple of 3.
((b+c)*a (b+c)*a (b+c)*a (b+c)*)*
26. Even no. of 0.
(1*01*01*)*
27. Odd no. of 1.
0*(10*10*)*10*
28. String should have odd length.
(0+1)((0+1)(0+1))*
29. String should have even length.
((0+1)(0+1))*
30. String start with 0 and has odd length.
0((0+1)(0+1))*
31. String start with 1 and has even length.
1(0+1)((0+1)(0+1))*
32. Even no of 1
Dixita Kagathara, CE Department | 2160704 – Theory of Computation 2
 Unit 2 – Regular Languages & Finite Automata

(0*10*10*)*
33. String of length 6 or less
(0+1+^)6
34. String ending with 1 and not contain 00.
(1+01)+
35. All string begins or ends with 00 or 11.
(00+11)(0+1)*+(0+1)*(00+11)
36. Language of all string containing both 11 and 00 as substring.
((0+1)*00(0+1)*11(0+1)*)+ ((0+1)*11(0+1)*00(0+1)*)
37. Language of C identifier.
(_+L)(_+L+D)*

2. Definition of Finite Automata.

A finite Automata or finite state machine is a 5-tuple(Q,∑,q0,A,δ) where,
Q is finite set of states;
∑ is finite alphabet of input symbols;
q0 ∈ Q (Initial state);
A (set of accepting states);
δ is a function from Q×∑Q(Transition function);
For any element q of Q and any symbol a ∈ ∑, we interpret δ (q, a) as the state to which the Finite
Automata moves, if it is in state q and receives the input a.
Application of finite automata
A finite automaton is used to solve several common types of computer algorithm. Some of them
are:
1. Design of digital circuit.
2. String matching.
3. Communication protocols for information exchange.
4. Lexical analysis phase of a compiler.

3. The Extended transition function δ* for FA.

Let M= (Q,∑,q0,A,δ) be an Finite Automata. We define the function δ*: Q×∑*Q as follow:
1) For any q ∈ Q, δ*(q,^)=q
2) For any q ∈ Q, y ∈ ∑*, and a ∈ ∑
δ*(q, ya)= δ(δ*(q, y),a)
Example:

a b c
q q1 q2 q3

Fig 2.1 Finite Automata

δ*(q,abc)
δ(δ*(q,ab),c)

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 3

 Unit 2 – Regular Languages & Finite Automata

δ(δ*( δ*(q,a),b),c)
δ(δ(δ* (q,^a),b),c)
δ(δ(δ(δ*(q,^),a),b),c)
δ(δ(δ(q,a),b),c)
δ(δ(q1,b),c)
δ(q2,c)
q3

4. Acceptance by an Finite Automata.

Let M= (Q1, ∑, q0, A, δ) be an FA. A string x ∈ ∑* is accepted by M if δ*(q0, x) ∈ A. If string is not
accepted, we can say it is rejected by M. The language accepted by M, or the language recognized
by M, is the set L(M) = {x ∈ ∑*/x is accepted by M} If L is any Language over ∑, L is accepted or
recognized by M if and only if L=L(M).

5. Draw Finite Automata for following:

1. The string with next to last symbol as 0.
0

1 C
0

A 0 B 1
1

1 0 D

Fig 2.2 Finite Automata for next to last symbol as 0

2. The string with number of 0s and number of 1s are odd

1
Odd 0 Odd 0
Odd 1 Even 1
1
0 0 0 0
1
Odd 1 Even 1
Even 0 Even 0
1
Fig 2.3 Finite Automata for number of 0s and number of 1s are odd

3. The string ending in 10 or 11.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 4

 Unit 2 – Regular Languages & Finite Automata

0 C
1
1 0
A B 0

0 1 D

Fig 2.4 Finite Automata for string ending in 10 or 11

4. The string corresponding to Regular expression {00}*{11}*

0,1
1
0 D
0
0 0 0 0
1
1
A B
1
1
1
Fig 2.5 Finite Automata for {00}*{11}*
5. (a+b)*baaa
b
a B
a
b

b
A C
b
b
a
a
a
E D

Fig 2.6 Finite Automata for (a+b)*baaa

6. Find a string of minimum length in {0,1}* not in the language

corresponding to the regular expression: 1*(0+10)*1*
The smallest string = 0110

7. Define Dead end state.

Dead state are those non accepting states whose transitions for every input symbols terminate

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 5

 Unit 2 – Regular Languages & Finite Automata

on themselves.

0, 1 0, 1 0,1 0, 1
q0 q1 q2 q3 q4

Fig 2.7 Dead end state

Ex: all strings of length at most 3. The string of length >3 should be rejected through a dead state
or a failure state. In above example dead state is q4.

8. Union, Intersection & Compliment operation on Finite Automata

Suppose M1=(Q1,∑,q1,A1,δ1)
M2=(Q2,∑,q2,A2,δ2)
Accept languages L1 and L2 respectively. Let M be an Finite Automata defined by
M=(Q,∑,q0,A,δ) where,
Q=Q1×Q2
q0=( q1, q2) and transition function δ is defined by the formula
δ((p,q),a)=(δ1(p,a), δ2(q,a)) for any p ∈ Q1 and q ∈ Q2 and a ∈ ∑ then
1) if A={(p,q) / p ∈ A1 or q ∈ A2}, M accept the language L1 U L2;
2) if A={(p,q) / p ∈ A1 and q ∈ A2}, M accept the language L1 ∩ L2;
3) if A={(p,q) / p ∈ A1 and q A2}, M accept the language L1 - L2.

9. Draw Finite Automata for following languages:

L1={x/x 00 is not substring of x, x ∈ {0,1}*}
L2={x/x ends with 01, x ∈ {0,1}*}
Draw finite Automata for L1 U L2, L1∩ L2 and L1-L2.
M1 1 0,1
0

A B 0
C

Fig 2.8 Finite Automata for 00 is not substring

M2
1 0

0 1
P Q R
0

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 6

 Unit 2 – Regular Languages & Finite Automata

Fig 2.9 Finite Automata for string ending in 01

Here Q1={A,B,C} and Q2={P,Q,R}
So,Q = Q1×Q2 ={AP,AQ,AR,BP,BQ,BR,CP,CQ,CR}
q0=(q1,q2)=(A,P)
δ((A,P),0) = (δ(A,0), δ(P,0))
= BQ
δ((A,P),1) = (δ(A,1), δ(P,1))
= AP
δ((B,Q),0) = (δ(B,0), δ(Q,0))
= CQ
δ((B,Q),1) = (δ(B,1), δ(Q,1))
= AR
δ((C,Q),0) = (δ(C,0), δ(Q,0))
= CQ
δ((C,Q),1) = (δ(C,1), δ(Q,1))
= CR
δ((A,R),0) = (δ(A,0), δ(R,0))
= BQ
δ((A,R),1) = (δ(A,1), δ(R,1))
= AP
δ((C,R),0) = (δ(C,0), δ(R,0))
= CQ
δ((C,R),1) = (δ(C,1), δ(R,1))
= CP
δ((C,P),0) = (δ(C,0), δ(P,0))
= CQ
δ((C,P),1) = (δ(C,1), δ(P,1))
= CP
L1-L2
0
0
1 BQ CQ
0 0 1
0
AP 0 0
1 1 CP

1 1
AR CR
Fig 2.10 Finite Automata for L1-L2

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 7

 Unit 2 – Regular Languages & Finite Automata

L1 U L2 0

1 BQ 1 CQ
1
0

AP 0 0 1 CP
1

1
1
AR CR

Fig. 2.11 Finite Automata for L1 U L2

L1∩ L2 0
1
1 BQ CQ
0 0 1

0 1 1
AP 0 CP

1
1
AR CR
Fig. 2.12 Finite Automata for L1∩ L2

10. Draw Finite Automata for following languages:

L1={x/x 11 is not substring of x, x ∈ {0,1}*}
L2={x/x ends with 10, x ∈ {0,1}*}
Draw finite Automata for L1∩ L2 and L1-L2.
(Most IMP)
M1
0 1
0, 1
1
A B C
0

Fig. 2.13 Finite Automata for 11 is not substring

M2
0 1

1 0
P Q R

1
0

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 8

 Unit 2 – Regular Languages & Finite Automata

Fig. 2.14 Finite Automata for string ending in 10

Here Q1={A,B,C}, Q2={P,Q,R}
So, Q = Q1×Q2 ={AP,AQ,AR,BP,BQ,BR,CP,CQ,CR}
q0=(q1,q2)
q0=(A,P)
δ((A,P),0) = (δ(A,0), δ(P,0))
= AP
δ((A,P),1) = (δ(A,1), δ(P,1))
= BQ
δ((B,Q),0) = (δ(B,0), δ(Q,0))
= AR
δ((B,Q),1) = (δ(B,1), δ(Q,1))
= CQ
δ((A,R),0) = (δ(A,0), δ(R,0))
= AP
δ((A,R),1) = (δ(A,1), δ(R,1))
= BQ
δ((C,Q),0) = (δ(C,0), δ(Q,0))
= CR
δ((C,Q),1) = (δ(C,1), δ(Q,1))
= CQ
δ((C,R),0) = (δ(C,0), δ(R,0))
= CP
δ((C,R),1) = (δ(C,1), δ(R,1))
= CQ
δ((C,P),0) = (δ(C,0), δ(P,0))
= CP
δ((C,P),1) = (δ(C,1), δ(P,1))
= CQ
L1 - L2
0 0

AP BP CP
1 0
1
1 1
AQ 1 BQ CQ
0

1
0
AR 0 BR CR

Fig. 2.15 Finite Automata for L1-L2

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 9

 Unit 2 – Regular Languages & Finite Automata

L1 ∩ L2
0 0

AP BP CP

1 0
1
1
AQ BQ 1 CQ
0 1
0
1
AR 0 BR CR

Fig. 2.16 Finite Automata for L1∩L2

11. Draw the Finite Automata recognizing the following

language
 L1 ∩ L2
 L1 - L2
L1
1
0,1
0 0
A B C

1
Fig. 2.17 Finite Automata
L2
1
0,1
0 0
A B C

Fig. 2.18 Finite Automata

Q1={A,B,C},Q2={A,B,C}
Q=Q1×Q2= {AA,AB,AC,BA,BB,BC,CA,CB,CC}
q0=(q1,q2) q0=(A,A)

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 10

 Unit 2 – Regular Languages & Finite Automata

δ((A,A),0) = (δ(A,0), δ(A,0))= BB

δ((A,A),1) = (δ(A,1), δ(A,1))= AA
δ((B,B),0) = (δ(B,0), δ(B,0))= CC
δ((B,B),1) = (δ(B,1), δ(B,1))= AA
δ((C,C),0) = (δ(C,0), δ(C,0))= CC
δ((C,C),1) = (δ(C,1), δ(C,1))= CC
L1 - L2
1

AA BA CA
0

AB BB CB
1

0
0,1
AC BC CC

Fig. 2.19 Finite Automata for L1-L2

L1 ∩ L2

1
0,1

AA 0 BB 0
CC

1
Fig. 2.20 Finite Automata for L1∩L2

12. Definition: Nondeterministic Finite Automata.

A nondeterministic finite automaton (NFA) is a 5-tuple (Q,Ʃ,q0,A,δ) Where Q and Ʃ are nonempty
finite sets, q0 ∈Q, A ⊆Q, and δ : Q × Ʃ2Q
Q is a finite set of states;
Ʃ is a finite set of input alphabets;
q0 ∈Q is the initial state;
A ⊆ Q is the set of accepting states;
δ :Q × (Ʃ∪ {Λ}) →2Q is the transition function.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 11

 Unit 2 – Regular Languages & Finite Automata

13. Definition: Non recursive Definition of δ* for an NFA.

For an NFA M=(Q,Ʃ, q0,A, δ), and any p ∈ Q, δ*(p, Λ)= {p}. For any p ∈ Q and x= a1a2….an ∈ Ʃ*
(with n≥1), δ*(p ,x) is the set of all states q for which there is a sequence of states p=p 0,p1,….pn-
1,pn = q satisfying
Pi ∈δ (pi-1 , ai) for each i with1 ≤ i ≤ n

14. Definition: Recursive Definition of δ* for an NFA

Let M=(Q,Ʃ, q0,A, δ), be an NFA. The function δ*: Q × Ʃ* 2Q is defined as follows.
1) For any q ∈ Q, δ*(q, Λ) = {q}.
2) For any q ∈ Q, y ∈Ʃ*, and a ∈Ʃ,
δ*(q, ya)= U δ(r, a)
r ∈δ*(q, y)

15. Definition: Acceptance by an NFA

Let M= (Q,Ʃ,q0,A,δ) be an NFA. The string x ∈Ʃ* is accepted by M if δ*(q0, x) ∩ A≠Ø. The language
recognized, or accepted, by M is the set L(M) of all string accepted by M. For any language L ⊆ Ʃ*,
L is recognized by M if L= L(M).

16. Using the Recursive Definition of δ* in an NFA.

Let M=(Q,Ʃ, q0,A, δ), where Q= {q0, q1, q2, q3}, Ʃ={0,1}, A= {q3}, and δ is given by the following
table:
q δ(q,0) δ(q,1)
q0 { q 0} { q0, q1}
q1 { q 2} { q 2}
q2 { q 3} { q 3}
q3 Ø Ø
Table 2.2 Transition Table

0,1
1 0,1 0,1
q0 q1 q2 q3

Fig. 2.21 NFA

Let us try to determine L(M) by calculating δ*( q 0,x) for a few string x of increasing length. First
observe that form the non recursive definition of δ* it is almost obvious that δ and δ* agree for
string of length 1. We see from the table that δ*( q0,0)={ q0} and δ*( q0,1)={ q0, q1};

δ*( q0,11) = U δ( r,1)

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 12
 Unit 2 – Regular Languages & Finite Automata

r∈δ*{ q0,1}

= U δ( r,1)
r∈{ q0, q1}
= δ{ q0,1}U δ( q1,1)
= { q0, q1}U{q2}
= { q 0, q 1, q 2}

δ*( q0,01) = U δ( r,1)

r∈δ*( q0,0)

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

δ*( q0,111) = U δ( r,1)

r∈δ*( q0,11)
= U δ( r,1)
r∈ (q0, q1, q2)

= δ(q0,1)U δ(q1,1)U δ(q2,1)

= {q0, q1, q2, q3}

δ*( q0,011) = U δ( r,1)

r∈δ*( q0,01)
= U δ( r,1)
r∈ (q0, q1)

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

17. Definition: A Nondeterministic Finite Automaton with Λ -

Transition.
A nondeterministic finite automata with Λ - Transition is a 5-tuple (Q,Ʃ, q0,A, δ), where Q and Ʃ
are finite sets, q0∈ Q, A ⊆Q, and δ : Q × (Ʃ∪ { Λ }) →2Q

18. Definition: Nondeterministic Definition of δ* for an NFA- Λ.

For an NFA- Λ M= (Q,Ʃ,q0,A, δ), states p,q∈ Q, and a string x = a1a2….an ∈Ʃ*, we will say M moves
from p to q by a sequence of transition corresponding to x if there exist an integer m ≥ n, a
sequence b1b2….bm ∈ Ʃ ∪ { Λ} satisfying b1b2….bm=x, and a sequence of states p= p0, p1… pm=q so
that for each i with 1 ≤ i ≤ m, pi ∈( pi-1 , bi ).

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 13

 Unit 2 – Regular Languages & Finite Automata

For x ∈ Ʃ* and p ∈δ*( p, x) is the set of all states q ∈ Q such that there is a sequence of
transition corresponding to x by which M moves from p to q.

19. Definition: Λ- Closure of a Set of States.

Let M=(Q,Ʃ, q0,A, δ), be an NFA – Λ, and let S ne any subset of Q. The Λ- closure of S is the set Λ(s)
defined as follows.
1) Every element of S is an element of Λ(s);
2) For any q ∈ Λ(s), every element of δ(q, Λ) is in Λ(s);
3) No other elements of Q are in Λ(s);

20. Definition: Recursive Definition of δ* for an NFA- Λ.

Let M= (Q, Ʃ, q0, A, δ) be an NFA – Λ, The extended transition function δ*: Q × Ʃ*→2Q is defined
as follows.
1) For any q ∈ Q, δ*(q, Λ) = Λ({q}).
2) For any q ∈ Q, y ∈Ʃ*, and a∈ Λ,
δ*(q,ya)= Λ( U δ(r,a))
r∈ δ*(q,y)
A string x is accepted by M if δ*(q0, x) ∩ A ≠ Ø. The language recognized by M is the set L(M) of all
strings accepted by M.

21. Compare FA, NFA and NFA-^.

Parameter NFA FA NFA-^
Transition Non deterministic Deterministic Non deterministic
Power NFA is as powerful FA is powerful as an It’s powerful as FA
as DFA NFA
Design Easy to design due More difficult to Allow flexibility in
to non-determinism design handling NFA
problem.
Acceptance It is difficult to find It is easy to find ^-transition is useful
whether w ∈ L as whether w ∈ L as in constructing a
there are several transition are composite FA with
paths. deterministic. respect to union,
Backtracking is concatenation, and
required to explore star.
several parallel
paths.
Table. 2.3 Difference between FA, NFA, NFA-^

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 14

 Unit 2 – Regular Languages & Finite Automata

22. Applying Definitions of ^(S) and δ*

0 1
0 1
P r S
^
^

^ W
q0

^ ^
0 0
t u v
1
0

Fig. 2.22 NFA-^

δ*(q0,^) = ^({q0})
= { q0,p,t}

δ*(q0,0) =^( U δ(r,0))

r∈δ*( q0,^)
= ^ (δ(q0,0) U δ(p,0) U δ(t,0))
= ^ (Ø U {p} U {u})
= ^ ({p,u})
= {p,u}

δ*(q0,01) =^( U δ(p,1))

r∈δ*( q0,0)
= ^ (δ(p,1)U δ(u,1))
= ^ ({r})
= {r}

δ*(q0,010) =^( U δ(p,0))

r∈δ*( q0,01)
= ^ (δ(r,0)
= ^({s})
= {s,w,q0,p,t}

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 15

 Unit 2 – Regular Languages & Finite Automata

23. Conversion from NFA to FA.

2
a b

1 b 4

a a
3

Fig. 2.23 NFA

δ*( 1,a) = {2,3}

δ*( 1,b) = {4}
q δ(q,a) δ(q,b)
δ*({2,3},a) = δ(2,a) U δ(3,a)
= {4} 1 {2,3} {4}
δ*({2,3},b) = δ(2,b) U δ(3,b) 2 {Ø} {4}
= {3,4} 3 {4} {3}
δ*(4,a) = {Ø}, 4 {Ø} {Ø}
δ*(4,b) = {Ø}
δ*({3,4},a) = δ(3,a) U δ(4,a) Table. 2.4 Transition Table
= {4}
δ*({3,4},b) = δ(3,b) U δ(4,b)
= {3}
δ*(3,a) = {4}
δ*(3,b) = {3}
a b 3,4
1 2, 3

b a a
b

4 3
a

Fig. 2.24 Finite Automata

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 16

 Unit 2 – Regular Languages & Finite Automata

24. Convert NFA - ^ to FA

q δ (q,^) δ (q,0) δ(q,1)
A {B} {A} Ø
B {D} {C} Ø
C Ø Ø {B}
D Ø {D} Ø
Table. 2.5 Transition Table

C
0 0
1
0
^ ^ D
A B

Fig. 2.25 NFA-^

δ*(A, ^) = {A,B,D}
δ*(A,0) = ^(U δ(r,0))
r∈ δ*( A,^)
= ^( U δ(r,0))
r∈(A,B,D)
= ^(δ(A,0)U δ(B,0)U δ(D,0))
= ^{A,C,D}
={A,B,C,D}
δ*(A,1) =^( U δ(r,1))
r∈ δ*( A,^)
=^( U δ(r,1))
r∈(A,B,D)
= ^ (δ(A,1) U δ(B,1) U δ(D,1))
=Ø

δ*(B,^) = {B,D}
δ*(B,0) = ^ ( U δ(r,0))
r∈δ*( B,^)
=^( U δ(r,0))
r∈δ(B,D)
= ^(δ(B,0)U δ(D,0))
= ^{ C,D}
= {C,D}
δ*(B,1) =^( U δ(r,1))
r∈δ*( B,˄)

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 17

 Unit 2 – Regular Languages & Finite Automata

=^( U δ(r,1))
r∈(B,D)
= ^(δ(B,1)U δ(D,1))
=Ø

δ*(C,˄) = {C}
δ*(C,0) =^( U δ(r,0))
r∈δ*( C,˄)
=^( U δ(r,0))
r∈(C)
= ^(δ(C,0))
=Ø
δ*(C,1) =^( U δ(r,1))
r∈δ*( C,˄)
=^( U δ(r,1))
r∈(C)
= ^(δ(C,1))
= ^{B}
= {B,D}

δ*(D,˄) = {D}
δ*(D,0) =^( U δ(r,0))
r∈δ*( D,^)
=^( U δ(r,0))
r∈(D)
= ^(δ(D,0))
= {D}
δ*(D,1) =^( U δ(r,1))
r∈δ*( D,^)
=^( U δ(r,1))
r∈(D)
= ^(δ(D,1))
=Ø

C
0 1
0
1 0
0
0 0
A B D
A
0

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 18

 Unit 2 – Regular Languages & Finite Automata

Fig. 2.26 NFA

δ({A},0) = {A,B,C,D}
δ({A},1) =Ø
δ({A,B,C,D},0) = (δ(A,0) U δ(B,0) U δ(C,0) U δ(D,0))
= {A,B,C,D}
δ({A,B,C,D},1) = (δ(A,1)U δ(B,1)U δ(C,1)U δ(D,1))
= {B,D}
δ({B,D},0) = (δ(B,0)U δ(D,0))
= {C,D}
δ({B,D},1) = (δ(B,1)U δ(D,1))
=Ø
δ({C,D},0) = (δ(C,0)U δ(D,0))
= {D}
δ({C,D},1) = (δ(C,1)U δ(D,1))
= {B,D}
δ({D},0) = {D}
δ({D},1) =Ø

0
1
ABCD BD
0
0
1
1 CD
A

1 0
Ø D
1
0,1 0
Fig. 1.27 Finite Automata

25. Convert NFA - ^ to FA

q δ (q,^) δ (q,0) δ(q,1)
A {B,D} {A} Ø
B Ø {C} {E}
C Ø Ø {B}
D Ø {E} {D}
E Ø Ø Ø
Table 2.6. Transition Table

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 19

 Unit 2 – Regular Languages & Finite Automata

1
0
0
^ B 1

A E

^
0
D
1

Fig. 2.28 NFA -^

δ*(A,^) = {A,B,D}
δ*(A,0) =^( U δ(r,0))
r∈δ*( A,^)
=^( U δ(r,0))
r∈δ(A,B,D)
= ^(δ(A,0)U δ(B,0)U δ(D,0))
= ^{A,C,E}
= {A,B,C,D,E}

δ*(A,1) =^( U δ(r,1))

r∈δ*( A,^)
=^( U δ(r,1))
r∈(A,B,D)
= ^(δ(A,1)U δ(B,1)U δ(D,1))
= ^(E,D)
= { ED}

δ*(B,^) = {B}
δ*(B,0) =^( U δ(r,0))
r∈δ*( B,^)
=^( U δ(r,0))
r∈δ (B)
= ^(δ(B,0))
= ^{ C}
= { C}
δ*(B,1) =^( U δ(r,1))
r∈δ*( B,^)

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 20

 Unit 2 – Regular Languages & Finite Automata

= ^( U δ(r,1))
r∈(B)
= ^(δ(B,1))
= {E}

δ*(C,^) = {C}
δ*(C,0) =^( U δ(r,0))
r∈δ*( C,^)
=^( U δ(r,0))
r∈(C)
= ^(δ(C,0))
=Ø
δ*(C,1) =^( U δ(r,1))
r∈δ*( C,^)
=^( U δ(r,1))
r∈(C)
= ^(δ(C,1))
= ^{B}
={B}
δ*(D,^)= {D}
δ*(D,0) =^( U δ(r,0))
r∈δ*( D,^)
=^( U δ(r,0))
r∈(D)
= ^(δ(D,0))
= ^ {E}
= {E}
δ*(D,1) =^( U δ(r,1))
r∈δ*( D,^)
=^( U δ(r,1))
r∈(D)
= ^(δ(D,1))
= {D}
δ*(E,^) ={E}
δ*(E,0) =Ø
δ*(E,1) =Ø

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 21

 Unit 2 – Regular Languages & Finite Automata

0 1
0

0 0 B 1

0,1
A E

0,1
0
D

Fig. 2.29 NFA

δ({A},0) = {A,B,C,D,E}
δ({A},1) = {ED}
δ({A,B,C,D,E},0) = (δ(A,0)U δ(B,0)U δ(C,0)U δ(D,0)U δ(E,0))
= {A,B,C,D,E}
δ({A,B,C,D,E},1) = (δ(A,1)U δ(B,1)U δ(C,1)U δ(D,1) U δ(E,0))
= {E,B,D}
δ({E,D},0) = (δ(E,0)U δ(D,0))
= {Ø}U{E}
= {E}
δ({E,D},1) = (δ(E,1)U δ(D,1))
= {Ø}U{D}
= {D}
δ({B,E,D},0) = (δ(B,0)Uδ(E,0)U δ(D,0))
= {C,E}
δ({B,E,D},1) = (δ(E,1)U δ(D,1))
= {D,E}
δ({C,E},0) = (δ(C,0)U δ(E,0))
=Ø
δ({C,E},1) = (δ(C,1)U δ(E,1))
= {B}
δ({D},0) = {E}
δ({D},1) = {D}
δ({B},0) = {C}
δ({B},1) = {E}
δ({E},0) =Ø
δ({E},1) =Ø

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 22

 Unit 2 – Regular Languages & Finite Automata

δ({C},0) =Ø
δ({C},1) = {B}

1 0
ABCDE BDE CE
0
0
1 0,1
0 1
A Ø C 1

1
0 0,1 0
DE B
E
1

1 0
D
1

Fig.2.30 Finite Automata

Kleene’s Theorem Part-1 or

26. Prove: Any Regular Language can be accepted by finite automata.
Proof:
 On the basis of statement L can be recognized by FA, NFA and NFA-^. It is sufficient to so that
every regular language can be accepted by NFA- ^.
 Set of regular language over alphabet Ʃ contains the basic languages. Ø, {^} and {a} (a ∈ Ʃ) to
be closed under operation of union, concatenation, and Kleene*.
 This allows us to prove using structural induction that every regular language over Ʃ can be
accepted by an NFA-^.
 The basis step of the proof is to show that the three basic languages can be accepted by NFA-
^s.
 The induction hypothesis is that L1 and L2 are languages that can be accepted by NFA-^s, and
the induction step is to show that L1 U L2, L1L2, and L1* can also be accepted by NFA-^s.
 NFA-^ for the three basic languages is shown below.

W a W

Ø {^} {a}
Dixita Kagathara, CE Department | 2160704 – Theory of Computation 23
 Unit 2 – Regular Languages & Finite Automata

Fig. 2.31 Basic Languages for NFA-^

 Now, suppose that L1 and L2 are recognized by the NFA-^s M1 and M2, respectively, where
for both i=1 and i=2,
Mi=(Qi,ε,qi,Ai,δi)
 By renaming state if necessary, we may assume that Q1 ∩ Q2 = Ø. We will construct NFA-^s
Mu, Mc, and Mk recognizing the language L1 U L2, L1L2, and L1*, respectively.
Construction Of Mu

f1
q1
f1’
^

qu
f2
^ q2
’
f2

Fig. 2.32 Construction Of Mu

 Construction of Mu = (Qu, ε,qu,Au,δu). Let qu be a new state, not in either Q1 or Q2 and let
Qu = Q1 U Q2 U { qu }
Au = A1 U A2
 Now, we define δu so that Mu can move from its initial state to either q1 or q2 by a ^
transition, and then make exactly the same moves that the respective M i would. Normally we
define:
δu(qu,^) = {q1,q2}
δu(qu,a) = Ø for every a ∈ ε
And for each q∈ Q1 U Q2 and a ∈ ε U {^},
δu(qu,a)={ δ1(q,a) if q ∈ Q1} and { δ2(q,a) if q ∈ Q2}
 For either value of i, if x∈ Li, then Mu can process x by moving to qi on a ^-transition and then
executing the moves that cause Mi to accept x, on the other hand, if x is accepted by M u,
there is a sequence of transition corresponding to x, starting at q u and ending at an element
of A1 or A2. The first of these transition must be a ^-transition from qu to either q1 or q2,
since there are no other transition from qu. therefore, since Q1 ∩ Q2 = Ø, either all the
transition are between of Q1 or all are between elements of Q 2. It follow that x must be
accepted by either M1 or M2.
Construction Of Mc
 Construction of Mc = (Qc, ε, qc, Ac, δc). In this case we do not need any new states, Let Qc = Q1
U Q2, qc=q1, and Ac = A2. The transition will include all those of M1 and M2 as well as a ε-
transition from each state in A1 to q2.
 In other words, for any q not in A1, and α ∈ ε U {^}, δc(q,a) is defined to be either δ1(q,a) or
δ2(q,a), depending on whether q is in Q1 and Q2, for q ∈ A1.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 24

 Unit 2 – Regular Languages & Finite Automata

δc(q,a)= δ1(q,a) for every a ∈ ε,

And δc(q,˄)= δ1(q,˄) U {q2}

f1 f2
^
qc=q1 q2
f1’ ^ f2’

Fig. 2.33 Construction Of Mc

 On an input string x1x2, where xi ∈ Li for both value of i, Mc can process x1, arriving at a state
A1; jump from this state to q2 by a ˄-transition; and then process x2 the way M2 would, So
that x1x2 is accepted. Conversely, if x is accepted by M c, there is a sequence of transition
corresponding to x that begins at q1 and ends at an element of A2. One of them must
therefore be from an element of Q1 to an element Q2, and according to the definition of δc,
this can only be a ˄- transition from an element of A1 to q2. Because Q1 ∩ Q2= Ø, all the
previous transition are between elements of Q1 and all the subsequent ones are between
elements of Q2. It follows that x=x1˄x2=x1x2, where x1 is accepted by M1 and x2 is accepted
by M2; in other words, x ∈ L1L2.
Construction Of Mk

q1
^ 1

qk

^ f1 f1’

Fig. 2.34 Construction Of Mk

 Construction of Mk = (Qk, Ʃ, qk, Ak,δk). Let qk be a new state not in Q1 and let Qk=Q1U{qk}.
Once again all the transitions of M1 will be allowed in M k, but in addition there is a ˄-
transition from qk to q1 and there is a ˄-transition from each elements of A1 to qk. More
precisely,
δk(qk,˄)={q1} and δk(qk,a)= Ø for a ∈ ε.
for q∈A1, δk(qk,˄)= δk(qk,˄) U {qk}.
 Suppose x∈L1*. if x=˄ then clearly x is accepted by Mk. Otherwise, for some m≥1,x=x1x2….xm,

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 25

 Unit 2 – Regular Languages & Finite Automata

where xi ∈ L1 for each i, Mk can move from qk to q1 by a ˄-transition; for each i, Mk moves
from q1 to an element fi of A1 by a sequence of transition corresponding to xi; and for each i,
Mk then moves from fi back to qk by a ˄-transition.
 It follows that (˄x1˄) (˄x2˄)…… (˄xm˄)=x is accepted by Mk. On the other hand, if x is
accepted by Mk, there is a sequence of transition corresponding to x that begins and ends at
qk. Since the only transition from qk is a ˄-transition to q1, and the only transition to qk are ˄-
transition from elements of A1, x can be decomposed in the form
x= (^x1˄) (˄x2˄)…… (˄xm˄)
 Where, for each i, there is a sequence of transition corresponding to xi from q1 to an element
of A1. Therefore, x∈ L1*.
 Since we have constructed an NFA-˄ recognizing L in each of the three cases, the proof is
complete.

27. Draw NFA-^ for following regular expression.

1. (00+1)*(10)*

0 ^ 0

^
^

1
^

^ ^ 1 ^ 0

Fig. 2.35 NFA-^ for (00+1)*(10)*

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 26

 Unit 2 – Regular Languages & Finite Automata

2. (0 + 1)* (10+01)* 11

^
0

^
^

1
^

^ ^
1 ^ 0
^
^
^

0 ^ 1
^

^
^

1 ^ 1

Fig. 2.36 NFA-^ for(0+1)*(10+01)*11

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 27

 Unit 2 – Regular Languages & Finite Automata

3. (0 + 1)* (10+110)* 1

^
0

^
^

1
^

^ 1 ^ 0
^
^
^

1 ^ 1 ^
^
0
0

Fig. 2.37 NFA-^ for(0+1)*(10+110)*1

28. Finite Automata with Output.

 Finite automata has limited capability of either accepting a string or rejecting a string.
 Accepance of string was based on the reachability of a machine from starting state to final
state. Finite automata can also be used as an output device.
 Such machines do not have a final state.
 Machine generates output on every input.
 There are two types of automata with outputs:
1. Moore machine
2. Mealy machine

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 28

 Unit 2 – Regular Languages & Finite Automata

29. Moore Machine

 Mathematiically moore machine is a six tuple machine and define as Mo=( Q,Ʃ, ∆, δ , /\’,q0)
where
Q: A Nonempty finite set of state in Mo
Ʃ: A Nonempty finite set of input symbols
∆: A Nonempty finite set of outputs
δ: It is transition function which takes two arguments as in finite automata, one is input state
and other is input symbol. The output of this function is a single state, so clearly δ is the
function which is responsible for the transition of Mo.
/\’: it is a mapping function which maps Q to ∆, giving the output associated with each state.

q0 : Is the initial state of Mo and q0 ∈ Q.

Examples of Moore Machine
1. Design a moore machine for the 1’s compliment of binary number.
1 0

0
A,0 B,1

Fig. 2.38 Moore M/c for 1’s compliment

2. Design a moore machine to count occurance of “ab” as substring.
b a

a b
A,0 B,0 C,1

a
b

Fig. 2.39 Moore M/c to count occurances of ab

3. Construct a moore machine that takes set of all strings over {0, 1} and produces ‘A’ if i/p
ends witg ‘10’ or produces ‘B’ if i/p ends with ’11’ otherwise produces ‘C’.
1
0

1 1
X,C Y,C Z,B

0 1
0 0

W,A
AA

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 29

 Unit 2 – Regular Languages & Finite Automata

Fig. 2.40 Moore M/c for string ending in 10 or 11

4. Construct a moore machine that takes binary number as an i/p and produces residue
modulo ‘3’ as an output.
0 1 ∆
q0 q0 q1 0
q1 q2 q0 1
q2 q1 q2 2
Table 2.7transition Table

0 1

1 0
q0,0 q1,1 q2,2

1 0
Fig. 2.41 Moore M/c to produces residue modulo ‘3’

30. Mealy Machine

 It is a finite automata in which output is associated with each transition.
 Mathematiically mealy machine is a six tuple machine and define as Me=( Q,Ʃ, ∆, δ , /\’,q0)
where
Q: A Nonempty finite set of state in Me
Ʃ: A Nonempty finite set of input symbols
∆: A Nonempty finite set of outputs
δ: It is transition function which takes two arguments as in moore machine, one is input state
and other is input symbol. The output of this function is a single state, so clearly δ is the
function which is responsible for the transition of Me.
/\’: it is a mapping function which maps Q x Ʃ to ∆, giving the output associated with each

transition.
q0 : Is the initial state of Me and q0 ∈ Q.

Examples of Mealy Machine

1. Design a mealy machine for the 1’s compliment of binary number.
0/1
1/0

Fig. 2.42 Mealy M/c for 1’s compliment of binary

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 30

 Unit 2 – Regular Languages & Finite Automata

2. Design a mealy machine for regular expression (0+1)*(00+11).

0/x

B
0/n

A 1/n
0/n

1/n
C

1/y
Fig. 2.43 Mealy M/c for (0+1)*(00+11)
3. Design a mealy machine where Ʃ={0, 1, 2} print residue modulo 5 of input treated as
ternary (base 3).
1/4

0/0 0/3
2/0 1/2

1/1 0/1 2/3 0/4

q0 q1 q2 q3 q4

2/2 1/3
2/1
2/4
0/2

1/0

Fig. 2.44 Mealy M/c to produces residue modulo ‘5’

31. Explain procedure to minimize Finite Automata

S-1: Make final state and non-final state as distinguish.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 31

 Unit 2 – Regular Languages & Finite Automata

S-2: Recursively interacting over the pairs of state for any transition for
δ(p,x) = r
δ(q,x) = s
and for x ∈ ε. If r and s are distinguishable make p and q as distinguish.
S-3: If any iteration over all possible state pairs one fails to find a new pair of states that are
distinguishable terminate.
S-4: All the states that are not distinguished are equivalence.

32. For following FA find minimized FA accepting same language.

a

a 4

2 b
a a
b 5
1
a
b
b a
6 b
3

b a

7
b

Fig. 2.45 Finite Automata

2
3 X X
4 X
5 X X X
6 X X X X X
7 X X X X
1 2 3 4 5 6

Final state is {6}

And, Non-Final state is {1,2,3,4,5,7}
(6, 1), (6,2), (6, 3), (6, 4), (6, 5), (6, 7) are distinguish pairs.
Consider pair (1,2)
δ(1,a)=2 δ(1,b)=3

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 32

 Unit 2 – Regular Languages & Finite Automata

δ(2,a)=4 δ(2,b)=5
Consider pair (1,3)
δ(1,a)=2 δ(1,b)=3
δ(3,a)=6 δ(3,b)=7
pair (2,6) is distinguish, so It’s a distinguished pair.
Consider pair (1,4)
δ(1,a)=2 δ(1,b)=3
δ(4,a)=4 δ(4,b)=5
Consider pair (1,5)
δ(1,a)=2 δ(1,b)=3
δ(5,a)=6 δ(5,b)=7
pair (2,6) is distinguish, so It’s a distinguished pair.
Consider pair (1,7)
δ(1,a)=2 δ(1,b)=3
δ(7,a)=6 δ(7,b)=7
pair (2,6) is distinguish, so It’s a distinguished pair.
Consider pair (2,3)
δ(2,a)=4 δ(2,b)=5
δ3(,a)=6 δ(3,b)=7
pair (4,6) is distinguish, so It’s a distinguished pair.
Consider pair (2,4)
δ(2,a)=4 δ(2,b)=5
δ(4,a)=4 δ(4,b)=5
Consider pair (2,5)
δ(2,a)=4 δ(2,b)=5
δ(5,a)=6 δ(5,b)=7
pair (4,6) is distinguish, so It’s a distinguished pair.
Consider pair (2,7)
δ(2,a)=4 δ(2,b)=5
δ(7,a)=6 δ(7,b)=7
pair (4,6) is distinguish, so It’s a distinguished pair.
Consider pair (3,4)
δ(3,a)=6 δ(3,b)=7
δ(4,a)=4 δ(4,b)=5
pair (6,4) is distinguish, so (3,4) is distinguish.
Consider pair (3,5)
δ(3,a)=6 δ(3,b)=7
δ(5,a)=6 δ(5,b)=7
Consider pair (3,7)
δ(3,a)=6 δ(3,b)=7
δ(7,a)=6 δ(7,b)=7
Consider pair (4,5)
δ(4,a)=4 δ(4,b)=5
Dixita Kagathara, CE Department | 2160704 – Theory of Computation 33
 Unit 2 – Regular Languages & Finite Automata

δ(5,a)=6 δ(5,b)=7
pair (6,4) is distinguish, so (4,5) is distinguish.
Consider pair (4,7)
δ(4,a)=4 δ(4,b)=5
δ(7,a)=6 δ(7,b)=7
pair (6,4) is distinguish, so (4,7) is distinguish.
Consider pair (5,7)
δ(5,a)=6 δ(5,b)=7
δ(7,a)=6 δ(7,b)=7

a b

b a
124 357 6

b
a
Fig. 2.46 Minimized Finite Automata

33. Define pumping lemma and its application.

Suppose L is a regular language. Then there is an integer n so that for any x∈ L with |x|>=n, there
are strings u, v, and w so that
1. x=uvw
2. |uv|<=n
3. |v|>0
4. For any m>=0, uvmw ∈ L

Application: (Explain the application of the Pumping Lemma to show a Language is Regular or Not)
The pumping lemma is extremely useful in proving that certain sets are non-regular. The general
methodology followed during its applications is :
 Select a string z in the language L.
 Break the string z into x, y and z in accordance with the above conditions imposed by the
pumping lemma.
 Now check if there is any contradiction to the pumping lemma for any value of i.
34. Use the pumping lemma to show that following language is not
regular: L = {ww|w ϵ {0,1}*}
Step 1: Let us assume that L is regular and L is accepted by an FA with n states.
Step 2: Let us chose the string
ῳ=anb anb
ῳ ῳ
| ῳ|=2n+2>=n
Let us write w as xyz with

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 34

 Unit 2 – Regular Languages & Finite Automata

|y|>0
And |xy|<=n
Since |xy|<=n, x must be of the form as.
Since |xy|<=n, y must be of the form ar | r>0
Now ῳ=anbanb= as ar an-s-rbanb
x y z
i
Step 3: Let us check whether x y z for i=2 belongs to L.
Xy2z= as a2r an-s-rbanb= an+rbanb
Since, r>0, an+rbanb is not of the form ῳῳ as the number of a’s in the first half is n+r and
second half is n. Therefore, xy2z L. Hence by contrdiction we can say language is not
regular.
35. Prove that the language L = {0n: n is a prime number} is not
regular.
Step 1: Let us assume that L is regular and L is accepted by an FA with n states.
Step 2: Let us chose the string
ῳ=ap ,where p is prime and p>n
| ῳ|= | ap| = p>=n
Let us write w as xyz with
|y|>0
And |xy|<=n
Since |xy|<=n, x must be of the form as.
We assume that y= am for m>0.
Step 3: Length of x yi z can be written as given below.
Xyiz= |xyz|+|yi-1|=p+(i-1)m
As |y|=| am |=m
Let us check whether P(i-1) m is prime for every i.
For i=p+1, p+(i-1)m= P+ Pm =P(1+m)
So xyp+1z L. Hence by contrdiction we can say language is not regular.
36. Use Pumping Lemma to show that following language is not
regular. L = { wwR / w ε {0,1}* }
Step 1: Let us assume that L is regular and L is accepted by an FA with n states.
Step 2: Let us chose the string
ῳ=anb ban
ῳ ῳR
| ῳ|=2n+2>=n
Let us write w as xyz with
|y|>0
And |xy|<=n
Since |xy|<=n, x must be of the form as.
Since |xy|<=n, y must be of the form ar | r>0
Now ῳ=anbban= as ar an-s-rbban
x y z
Dixita Kagathara, CE Department | 2160704 – Theory of Computation 35
 Unit 2 – Regular Languages & Finite Automata

Step 3: Let us check whether x yi z for i=2 belongs to L.

Xy2z= as a2r an-s-rbban= an+rbban
Since, r>0, an+rbban is not of the form ῳῳR as the string starts with (n+r) a’s but ends in (n)
a’s. Therefore, Xy2z L. Hence by contrdiction we can say language is not regular.

Dixita Kagathara, CE Department | 2160704 – Theory of Computation 36