P. A.
COLLEGE OF ENGINEERING AND TE
CHNOLOGY
An Autonomous Institution
Accredited by NAAC with ‘A’ Grade
POLLACHI – 642 002
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Accredited by NBA
ODD SEMESTER 2023-2024
Year of study & III/VI
Academic Year : 2024-2025 :
Semester IT
Course Code &
22CAPC504 THEORY OF COMPUTATION
Title :
ASSIGNMENT II
ANSWER KEY
1.Convert the given NFA to its equivalent DFA.
2. Construct FA for the following table, test whether the strings 101101,11111 are
accepted or not.
STATE 0 1
q0 q0 q1
q1 q3 q0
q2 q0 q3
q3 q1 Q2
3. Explain the DFA Minimization algorithm with an example.
Minimization of DFA means reducing the number of states from given FA. Thus, we get the
FSM(finite state machine) with redundant states after minimizing the FSM.
We have to follow the various steps to minimize the DFA. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the
transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states,
and T2 contains non-final states.
Step 4: Find similar rows from T1 such that:
1. δ (q, a) = p
2. δ (r, a) = p
That means, find the two states which have the same value of a and b and remove one of
them.
Step 5: Repeat step 3 until we find no similar rows available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the
transition table of minimized DFA
Example:
Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.
Step 2: Draw the transition table for the rest of the states.
State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q5 q5
*q5 q5 q5
Step 3: Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final states:
State 0 1
q0 q1 q3
q1 q0 q3
2. Another set contains those rows, which starts from final states.
State 0 1
q3 q5 q5
q5 q5 q5
Step 4: Set 1 has no similar rows so set 1 will be the same.
Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and
1. So skip q5 and then replace q5 by q3 in the rest.
State 0 1
q3 q3 q3
Step 6: Now combine set 1 and set 2 as:
State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q3 q3
Now it is the transition table of minimized DFA.
4. Construct an NFA equivalent to the following RE.((10)+(0+1)*)01.
BATCH 2
1. How can you eliminate ε-transitions from a given ε-NFA to convert it into an
equivalent NFA without ε-transitions?
δ'(q0, 0) = ε-closure(δ(δ^(q0, ε),0))
= ε-closure(δ(ε-closure(q0),0))
= ε-closure(δ(q0, 0) ∪ δ(q1, 0) U δ(q2, 0) )
= ε-closure(δ(q0,q1,q2), 0))
= ε-closure(q0 U Φ ∪ Φ)
= ε-closure(q0)
= {q0,q1, q2}
δ'(q0, 1) = ε-closure(δ(δ^(q0, ε),1))
= ε-closure(δ(q0, 1) ∪ δ(q1, 1) U δ(q2, 1) )
= ε-closure(δ(q0,q1,q2), 1))
= ε-closure(Φ ∪q1 U Φ)
= ε-closure(q1)
= {q1, q2}
δ'(q0, 2) = ε-closure(δ(δ^(q0, ε),2))
= ε-closure(δ(q0, 2) ∪ δ(q1, 2) U δ(q2, 2) )
= ε-closure(δ(q0,q1,q2), 2))
= ε-closure(Φ U ΦU q2)
= ε-closure(q2)
= {q2}
δ'(q1, 0) = ε-closure(δ(δ^(q1, ε),0))
= ε-closure(δ(q1,q2), 0))
= ε-closure(Φ ∪ Φ)
= ε-closure(δ(q1, 0) U δ(q2, 0) )
= ε-closure(Φ)
=Φ
δ'(q1,1) = ε-closure(δ(δ^(q1, ε),1))
= ε-closure(δ(q1,q2), 1))
= ε-closure(q1 ∪ Φ)
= ε-closure(δ(q1, 1) U δ(q2, 1) )
= ε-closure(q1)
= {q1,q2}
δ'(q1, 2) = ε-closure(δ(δ^(q1, ε),2))
= ε-closure(δ(q1,q2), 2))
= ε-closure(Φ ∪ q2)
= ε-closure(δ(q1, 2) U δ(q2, 2) )
= ε-closure(q2)
= {q2}
δ'(q2, 0) = ε-closure(δ(δ^(q2, ε),0))
= ε-closure(δ(q2), 0))
= ε-closure(δ(q2, 0))
= ε-closure(Φ)
=Φ
δ'(q2, 1) = ε-closure(δ(δ^(q2, ε),1))
= ε-closure(δ(q2), 1)
= ε-closure(δ(q2, 1))
= ε-closure(Φ)
=Φ
δ'(q2, 2) = ε-closure(δ(δ^(q2, ε),))
= ε-closure(δ(q2), 2))
= ε-closure(δ(q2, 2))
= ε-closure(q2)
= {q2}
Now, we will summarize all the computed δ' transitions as given below −
δ'(q0,0)={q0,q1,q2}
δ'(q0,1)={q1,q2}
δ'(q0,2)={q2}
δ'(q1,0)= { Φ }
δ'(q1,1)={q1,q2}
δ'(q1,2)={q2}
δ'(q2,0)={ Φ }
δ'(q2,1)={ Φ }
δ'(q2,2)={q2}
The transition table is given below −
States 0 1 2
q0 {q0,q1,q2} {q1,q2} {q2}
q1 Φ {q1,q2} {q2}
q2 Φ Φ {q2}
The NFA without epsilon is given below
2. Draw a deterministic and non-deterministic finite automate which accept 00 and 11
at the end of a string containing 0, 1 in it, e.g., 01010100 but not 000111010.
Design a DFA and NFA of a same string if input value reaches the final state then it is
acceptable otherwise it is not acceptable.
DFA of the given string is as follows
3. Explain the DFA Minimization algorithm with an example.
Minimization of DFA means reducing the number of states from given FA. Thus, we get the
FSM(finite state machine) with redundant states after minimizing the FSM.
We have to follow the various steps to minimize the DFA. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the
transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states,
and T2 contains non-final states.
Step 4: Find similar rows from T1 such that:
1. δ (q, a) = p
2. δ (r, a) = p
That means, find the two states which have the same value of a and b and remove one of
them.
Step 5: Repeat step 3 until we find no similar rows available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the
transition table of minimized DFA
Example:
Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.
Step 2: Draw the transition table for the rest of the states.
State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q5 q5
*q5 q5 q5
Step 3: Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final states:
State 0 1
q0 q1 q3
q1 q0 q3
2. Another set contains those rows, which starts from final states.
State 0 1
q3 q5 q5
q5 q5 q5
Step 4: Set 1 has no similar rows so set 1 will be the same.
Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and
1. So skip q5 and then replace q5 by q3 in the rest.
State 0 1
q3 q3 q3
Step 6: Now combine set 1 and set 2 as:
State 0 1
→q0 q1 q3
q1 q0 q3
*q3 q3 q3
Now it is the transition table of minimized DFA.
4. Construct NFA for RE b+ba*
Faculty in charge HOD
