[go: up one dir, main page]
Scribd
Upload
315 views7 pages

NFA To DFA Subset Construction Notes Module 2

1. The document describes converting an NFA to a DFA using the subset construction method. It gives an example NFA with states q0, q1, q2, q3 and transitions. 2. It shows constructing the DFA state subsets from the NFA states and transitions. Transitions between DFA states are determined from the NFA transitions. 3. The resulting DFA has states [q0], [q1], [q2], [q3] with transitions defined based on the NFA transitions between subsets of states.

Uploaded by

Sindhu P
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
315 views7 pages

NFA To DFA Subset Construction Notes Module 2

1. The document describes converting an NFA to a DFA using the subset construction method. It gives an example NFA with states q0, q1, q2, q3 and transitions. 2. It shows constructing the DFA state subsets from the NFA states and transitions. Transitions between DFA states are determined from the NFA transitions. 3. The resulting DFA has states [q0], [q1], [q2], [q3] with transitions defined based on the NFA transitions between subsets of states.

Uploaded by

Sindhu P
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

1.

Convert the following NFA to DFA using the subset construction


method

a,b

q0 a q1

NFA Transition Table

δ a b

 q0 { q1 } φ

*q1 {q1} {q1}


DFA Transition Table

δ a b

 [q0] [q1] [D]

[D] [D] [D]

* [q1] [q1] [q1]

δ([q0],a)= [q1] if δ(q0,a)={q1}


δ([q0],b)= [D] if δ(q0,b)={}
δ([q1],a)= [q1] if δ(q1,a)={q1}
δ([q1],b)= [q1] if δ(q1,b)={q1}
a, b

a
[q0] [q1]

[D]

a, b

1. Convert the following NFA to DFA using the subset construction


method

a, b

a a
b
q3
q0 q1 q2
Step 1

NFA Table
δ a b

->q0 {q1} φ

q1 φ {q2}

q2 {q3} φ

*q3 {q3} {q3}

Step 2
DFA Table

δ a b

 [q0] [q1] [D]

[D] [D] [D]

[q1] [D] [q2]

[q2] [q3] [D]

*[q3] [q3] [q3]


a, b

a b a
[q0 [q1] [q2] [q3]
]

b
b

[D]
a, b
DFA Transition Table of DFA
δ 0 1

 [p] [p,q] [p]

[p,q] [p,q,r] [p,r]


[p,r] [p,q,s] [p]
[p,q,r] [p,q,r,s] [p,r]
*[p,q,s] [p,q,r,s] [p,r,s]
*[p,q,r,s] [p,q,r,s] [p,r,s]
*[p,r,s] [p,q,s] [p,s]
*[p,s] [p,q,s] [p,s]
δ([p,q],0)= [p,q,r] if δ(p,0)∪δ(q,0)={p,q}∪{r}={p,q,r}
Complete the remaining transitions by yourself using the same method

0 0 0

[p] [p,q] [p,q,r]


[p,q,r,s]

1
1

[p,r]

[p,q,s] 0

0
0 0
1
1

1
[p,s]
[p,r,s]
1

You might also like