Compiler Design

BITS Pilani
Pilani | Dubai | Goa | Hyderabad
 BITS Pilani
Pilani | Dubai | Goa | Hyderabad

Contact Session - 3
Introduction to Lexical Analyzer
IMP Note to Self

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 IMP Note to Students
➢ It is important to know that just login to the session does not
guarantee the attendance.
➢ Once you join the session, continue till the end to consider yo
u as present in the class.
➢ IMPORTANTLY, you need to make the class more interactive b
y responding to Professors queries in the session.
➢ Whenever Professor calls your number / name ,you need to
respond, otherwise it will be considered as ABSENT

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Objective
• Recap the Regular Expression
• Hierarchy of languages
• Deterministic Finite State Automata

5
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Hierarchy of languages

Non-Recursively Enumerable Languages

Recursively Enumerable Languages

Recursive Languages

Context-Free Languages

Regular Languages

6
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Deterministic Finite State Automata (DFA)
……..
0 1 1 0 0

Finite
Control
• One-way, infinite tape, broken into cells
• One-way, read-only tape head.
• Finite control, i.e.,
– finite number of states, and
– transition rules between them, i.e.,
– a program, containing the position of the read head, current symbol being scanne
d, and the current “state.”
• A string is placed on the tape, read head is positioned at the left end,
and the DFA will read the string one symbol at a time until all symbols
have been read. The DFA will then either accept or reject the string.
7
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• The finite control can be described by a transition diagram or table:
• Example #1:
1

0
q0 q1 1
0
1 0 0 1 1
q0 q0 q1 q0 q0 q0

• One state is final/accepting, all others are rejecting.

• The above DFA accepts those strings that contain an even number of
0’s, including the null string, over Sigma = {0,1}
L = {all strings with zero or more 0’s}
• Note, the DFA must reject all other strings
8
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Note:
• Machine is for accepting a language, language is the purpose!

• Many equivalent machines may accept the same language,

but a machine cannot accept multiple languages!

M1 M2 …. M-inf

• Id’s of the characters or states are irrelevant,

you can call them by any names!
Sigma = {0, 1} ≡ {a, b}
States = {q0, q1} ≡ {u, v}, as long as they have
identical (isomorphic) transition table
9
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• An equivalent machine to the previous example (DFA for even numbe
r of 0’s):

1 1
q3 q2

1 0 0 0

q0 0 q1 1

1 0 0 1 1
q0 q3 q1 q2 q2 q2 accept string

• One state is final/accepting, all others are rejecting.

• The above DFA accepts those strings that contain an even number of
0’s, including null string, over Sigma = {0,1}
• Can you draw a machine for a language by excluding the null string fr
om the language? L = {all strings with 2 or more 0’s}
10
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Example #2:

a a a/b/c

c c
q0 q1 q2

b b

a c c c b accepted
q0 q0 q1 q2 q2 q2

a a c rejected
q0 q0 q0 q1

• Accepts those strings that contain at least two c’s

11
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 a a a/b/c
q0 c q1 c q2

b b
Inductive Proof (sketch): that the machine correctly accepts strings with at least two c’s
Proof goes over the length of the string.

Base: x a string with |x|=0. state will be q0 => rejected.

Inductive hypothesis: |x|= integer k, & string x is rejected - in state q0 (x must have zero c),
OR, rejected – in state q1 (x must have one c),
OR, accepted – in state q2 (x has already with two c’s)

Inductive steps: Each case for symbol p, for string xp (|xp| = k+1), the last symbol p = a, b or c

xa xb xc

x ends in q0 q0 =>reject q0 =>reject q1 =>reject

(still zero c => should (still zero c => should (still zero c => should
reject) reject) reject)
x ends in q1 q1 =>reject q1 =>reject q2 =>accept
(still one c => should (still one c => should (two c now=> should
reject) reject) accept)
x ends in q2 q2 =>accept q2 =>accept q2 =>accept
(two c already => (two c already => (two c already =>
should accept) should accept) should accept)
12
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Formal Definition of a DFA

• A DFA is a five-tuple:

M = (Q, Σ, δ, q0, F)

Q A finite set of states

Σ A finite input alphabet
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A transition function, which is a total function from Q x Σ to Q

δ: (Q x Σ) –> Q δ is defined for any q in Q and s in Σ, and

δ(q,s) = q’ is equal to some state q’ in Q, could be q’=q

Intuitively, δ(q,s) is the state entered by M after reading symbol s while in sta
te q.
13
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Revisit example #1: 1

Q = {q0, q1} 0
Σ = {0, 1} q0 q1 1
Start state is q0 0
F = {q0}

δ:
0 1
q0 q1 q0

q1 q0 q1

14
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Revisit example #2:

a a a/b/c
Q = {q0, q1, q2}
Σ = {a, b, c} c c
q0 q1 q2
Start state is q0
F = {q2} b b

δ: a b c
q0 q0 q0 q1

q1 q1 q1 q2

q2 q2 q2 q2

• Since δ is a function, at each step M has exactly one option.

• It follows that for a given string, there is exactly one computation.

15
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Extension of δ to Strings

δ^ : (Q x Σ*) –> Q

δ^(q,w) – The state entered after reading string w having started in state
q.

Formally:

1) δ^(q, ε) = q, and
2) For all w in Σ* and a in Σ
δ^(q,wa) = δ (δ^(q,w), a)

16
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Recall Example #1: 1

0
q0 q1 1
0
• What is δ^(q0, 011)? Informally, it is the state entered by M after proc
essing 011 having started in state q0.
• Formally:

δ^(q0, 011) = δ (δ^(q0,01), 1) by rule #2

= δ (δ ( δ^(q0,0), 1), 1) by rule #2
= δ (δ (δ (δ^(q0, λ), 0), 1), 1) by rule #2
= δ (δ (δ(q0,0), 1), 1) by rule #1
= δ (δ (q1, 1), 1) by definition of δ
= δ (q1, 1) by definition of δ
= q1 by definition of δ

• Is 011 accepted? No, since δ^(q0, 011) = q1 is not a final state. 17

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Note that:

δ^ (q,a) = δ(δ^(q, ε), a) by definition of δ^, rule #2

= δ(q, a) by definition of δ^, rule #1

• Therefore:

δ^ (q, a1a2…an) = δ(δ(…δ(δ(q, a1), a2)…), an)

• However, we will abuse notations, and use δ in place of δ^:

δ^(q, a1a2…an) = δ(q, a1a2…an)

18
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Example #3:
1 1 1
0
0
q0 q1 q2
0
• What is δ(q0, 011)? Informally, it is the state entered by M after proce
ssing 011 having started in state q0.
• Formally:
δ(q0, 011) = δ (δ(q0,01), 1) by rule #2
= δ (δ (δ(q0,0), 1), 1) by rule #2
= δ (δ (q1, 1), 1) by definition of δ
= δ (q1, 1) by definition of δ
= q1 by definition of δ

• Is 011 accepted? No, since δ(q0, 011) = q1 is not a final state.

• Language?
• L ={ all strings over {0,1} that has 2 or more 0 symbols}
19
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Recall Example #3:
1 1 1
0
0
q0 q1 q2
0

• What is δ(q1, 10)?

δ(q1, 10) = δ (δ(q1,1), 0) by rule #2

= δ (q1, 0) by definition of δ
= q2 by definition of δ

• Is 10 accepted? No, since δ(q0, 10) = q1 is not a final state. The fact tha
t δ(q1, 10) = q2 is irrelevant, q1 is not the start state!

20
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Definitions related to DFAs
• Let M = (Q, Σ, δ,q0,F) be a DFA and let w be in Σ*. Then w is accepted by M if
f δ(q0,w) = p for some state p in F.

• Let M = (Q, Σ, δ,q0,F) be a DFA. Then the language accepted by M is the set:

L(M) = {w | w is in Σ* and δ(q0,w) is in F}

• Another equivalent definition:

L(M) = {w | w is in Σ* and w is accepted by M}

• Let L be a language. Then L is a regular language iff there exists a DFA M s

uch that L = L(M).

• Let M1 = (Q1, Σ1, δ1, q0, F1) and M2 = (Q2, Σ2, δ2, p0, F2) be DFAs. Then M1 and
M2 are equivalent iff L(M1) = L(M2).

21
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Notes:
– A DFA M = (Q, Σ, δ,q0,F) partitions the set Σ* into two sets: L(M) and
Σ* - L(M).

– If L = L(M) then L is a subset of L(M) and L(M) is a subset of L (def. of set equality).

– Similarly, if L(M1) = L(M2) then L(M1) is a subset of L(M2) and L(M2) is a subset of L(
M1).

– Some languages are regular, others are not. For example, if

Regular: L1 = {x | x is a string of 0's and 1's containing an even

number of 1's} and

Not-regular: L2 = {x | x = 0n1n for some n >= 0}

• Can you write a program to “simulate” a given DFA, or any arbitrary input DFA?

• Question we will address later:

– How do we determine whether or not a given language is regular?

22
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Give a DFA M such that:

L(M) = {x | x is a string of 0’s and 1’s and |x| >= 2}

0/1

0/1 0/1
q0 q1 q2

Prove this by induction

23
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Give a DFA M such that:

L(M) = {x | x is a string of (zero or more) a’s, b’s and c’s such

that x does not contain the substring aa}

b/c a/b/c
a
a
q0 q1 q2
b/c

Logic:
In Start state (q0): b’s and c’s: ignore – stay in same state
q0 is also “accept” state
First ‘a’ appears: get ready (q1) to reject
But followed by a ‘b’ or ‘c’: go back to start state q0
When second ‘a’ appears after the “ready” state: go to reject state q2
Ignore everything after getting to the “reject” state q2
24
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Give a DFA M such that:

L(M) = {x | x is a string of a’s, b’s and c’s such that x

contains the substring aba}

b/c a a/b/c
a a
b
q0 q1 q2 q3
c

b/c
Logic: acceptance is straight forward, progressing on each expected sym
bol
However, rejection needs special care, in each state (for DFA, we will see t
his becomes easier in NFA, non-deterministic machine)

25
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Give a DFA M such that:

L(M) = {x | x is a string of a’s and b’s such that x

contains both aa and bb}
First do, for a language where ‘aa’ comes before ‘bb’
Then do its reverse; and then parallelize them.
a
b
a
q1 q2 q3 b
a a/b
a

q0 a b q7
b
b a
b a
q4 q5 q6
b

Remember, you may have multiple “final” states, but only one “start” stat
e
26
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Let Σ = {0, 1}. Give DFAs for {}, {ε}, Σ*, and Σ+.

For {}: For {ε}:

0/1
0/1
0/1
q0 q0 q1

For Σ*: For Σ+:

0/1 0/1

0/1
q0 q0 q1

27
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Problem: Third symbol from last is 1

0/1

1 0/1 0/1
q0 q1 q2 q3

Is this a DFA?

No, but it is a Non-deterministic Finite Automaton

28
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Practice problem 1
• Draw a DFA for the language accepting strings starting with ‘ab’ over input alphab
ets ∑ = {a, b}
– Solution:
– Step-01:
• All strings of the language starts with substring “ab”. So, length of substring =
2.
– Thus, Minimum number of states required in the DFA = 2 + 2 = 4.
– It suggests that minimized DFA will have 4 states.
– Step-02:
– We will construct DFA for the following strings-
• ab
• aba
• abab

29
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Step 3

30
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Practice problem 2
• Construct a DFA that accepts a language L over input alphabet
s ∑ = {a, b} such that L is the set of all strings starting with ‘aa’
or ‘bb’.
• Step-01:
• Minimum number of states required in the DFA = 5.
• It suggests that minimized DFA will have 5 states.
• Step-02:
• We will construct DFA for the following strings-
• aa
• aaa
• aaaa
• bb
• bbb
• bbbb
31
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• Step 3

32
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Practice problem 3
• Let Σ = {a, b} and let L = { w ∈ Σ* | w ≠ ε and the first and last c
haracter of w are the same }. Design a DFA for L.

33
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Practice problem 4
• Let Σ = {a, b} and let L = { w ∈ Σ* | w is a nonempty string who
se characters alternate between a's and b's }. Design a DFA w
hose language is L.

34
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Nondeterministic Finite Automata

Nondeterminism
Subset Construction

35
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Nondeterminism
• A nondeterministic finite automaton has the a
bility to be in several states at once.
• Transitions from a state on an input symbol ca
n be to any set of states.

36
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Nondeterminism – (2)
• Start in one start state.
• Accept if any sequence of choices leads to a
final state.
• Intuitively: the NFA always “guesses right.”

37
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Formal NFA
• A finite set of states, typically Q.
• An input alphabet, typically Σ.
• A transition function, typically δ.
• A start state in Q, typically q0.
• A set of final states F ⊆ Q.

38
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Transition Function of an NFA
• δ(q, a) is a set of states.
• Extend to strings as follows:
• Basis: δ(q, ε) = {q}
• Induction: δ(q, wa) = the union over all states
p in δ(q, w) of δ(p, a)

39
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Language of an NFA
• A string w is accepted by an NFA if δ(q0, w) co
ntains at least one final state.
• The language of the NFA is the set of strings it
accepts.

40
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Equivalence of DFA’s, NFA’s

• A DFA can be turned into an NFA that accepts

the same language.
• If δD(q, a) = p, let the NFA have δN(q, a) = {p}.
• Then the NFA is always in a set containing
exactly one state – the state the DFA is in after
reading the same input.

41
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Equivalence – (2)

• Surprisingly, for any NFA there is a DFA that

accepts the same language.
• Proof is the subset construction.
• The number of states of the DFA can be exp
onential in the number of states of the NFA
• Thus, NFA’s accept exactly the regular lang
uages.

42
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Subset Construction

• Given an NFA with states Q, inputs Σ, transit

ion function δN, state state q0, and final stat
es F, construct equivalent DFA with:
– States 2Q (Set of subsets of Q).
– Inputs Σ.
– Start state {q0}.
– Final states = all those with a member of F.

43
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Critical Point

• The DFA states have names that are sets of

NFA states.
• But as a DFA state, an expression like {p,q}
must be read as a single symbol, not as a set
• Analogy: a class of objects whose values are
sets of objects of another class.

44
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Subset Construction – (2)
• The transition function δD is defined by:
δD({q1,…,qk}, a) is the union over all i = 1,…,k of
δN(qi, a).
• Example: We’ll construct the DFA equivalent o
f our “chessboard” NFA.

45
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4}
3 2,6 5 {5}
4 2,8 1,5,7
5 2,4,6,8 1,3,7,9
6 2,8 3,5,9
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5 Alert: What we’re doing here is
the lazy form of DFA construction,
where we only construct a state
if we are forced to.
46
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5}
4 2,8 1,5,7 {2,4,6,8}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5

47
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5

48
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8} {2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

49
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8} {2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7} {2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

50
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8} {2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7} {2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9} {2,4,6,8} {5}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

51
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: Subset Construction
r b r b

1 2,4 5 {1} {2,4} {5}

2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8} {2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7} {2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9} {2,4,6,8} {5}
7 4,8 5 * {1,3,5,7,9} {2,4,6,8} {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

52
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 NFA’s With ε-Transitions
• We can allow state-to-state transitions on ε in
put.
• These transitions are done spontaneously, wit
hout looking at the input string.
• A convenience at times, but still only regular l
anguages are accepted.

53
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Example: ε-NFA

ε 0 1 ε
A {E} {B} ∅
1 1 B ∅ {C} {D}
1 B C D C ∅ {D} ∅
D ∅ ∅ ∅
A ε ε 0
* E
F
{F} ∅ {B, C}
{D} ∅ ∅
0
E F
0

54
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Closure of States

• CL(q) = set of states you can reach from sta

te q following only arcs labeled ε.
• Example: CL(A) = {A}; ε
1 1
1 B C D
CL(E) = {B, C, D, E}.
A ε ε 0
0 E F
• Closure of a set of states = union of the clos 0

ure of each state.

55
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Equivalence of NFA, ε-NFA
• Every NFA is an ε-NFA.
– It just has no transitions on ε.
• Converse requires us to take an ε-NFA and co
nstruct an NFA that accepts the same languag
e.
• We do so by combining ε–transitions with the
next transition on a real input.

Warning: This treatment is a

bit different from that in the text.
56
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Picture of ε-Transition Removal

a
Transitions
on ε
Transitions
on ε

57
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Picture of ε-Transition Removal
To here, and performs
Text goes
the subset construction
from here

a
Transitions
on ε
Transitions
on ε

58
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Picture of ε-Transition Removal
To here, with no
subset construction

a
We’ll go
from here
a

a
Transitions
on ε
Transitions
on ε

59
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Equivalence – (2)
• Start with an ε-NFA with states Q, inputs Σ, st
art state q0, final states F, and transition functi
on δE.
• Construct an “ordinary” NFA with states Q, inp
uts Σ, start state q0, final states F’, and transiti
on function δN.

60
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Equivalence – (3)

• Compute δN(q, a) as follows:

1. Let S = CL(q).
2. δN(q, a) is the union over all p in S of δE(p, a).
• F’ = the set of states q such that CL(q) con
tains a state of F.
• Intuition: δN incorporates ε–transitions b
efore using a but not after.

61
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Interesting closures:

Example: ε-NFA-to-NFA
CL(B) = {B,D};
CL(E) = {B,C,D,E}

0 1 ε 0 1
A {E} {B} ∅ A {E} {B}
B ∅ {C} {D} * B ∅ {C}
C ∅ {D} ∅ C ∅ {D}
D ∅ ∅ ∅ D ∅ ∅
*
* E {F} ∅ {B, C} E {F} {C, D}
F {D} ∅ ∅ * F {D} ∅

ε-NFA
Since closure of
E includes B and
Since closures of C; which have
B and E include transitions on 1
final state D. to C and D.

62
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
 Summary
• DFA’s, NFA’s, and ε–NFA’s all accept exactly th
e same set of languages: the regular language
s.
• The NFA types are easier to design and may h
ave exponentially fewer states than a DFA.
• But only a DFA can be implemented!

63
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
• https://www.gatevidyalay.com/tag/dfa-exam
ples-with-solutions-pdf/
• https://web.stanford.edu/class/cs103a/ass
n/070S%20Solutions%20for%20Practice%
20with%20Automata.pdf
• https://www.cse.iitd.ac.in/~naveen/courses/C
OL352/slides/fa3.ppt

64
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
IMP Note to Self

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Thank you

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956