Subset construction to build DFA equivalent to NFA below.

Question

Use subset construction to build a DFA equivalent to the NFA below. Show your work.
Note: ε is the epsilon symbol.

	a	b	ε
1	{2,5}	{1,3}	{}
2	{2}	{3}	{4}
3	{5}	{}	{}
4	{}	{4}	{3}
5*	{}	{}	{}

Note: Here ‘*’ shows the final state

Summary

We have given the NFA, which has a total of five states with one final state. Similar to the DFA, it has in total nine states with two final states. where DFA is equivalent to NFA.
initially in the obtained DFA, for each input, there is only one output state for all the states. And there is none have a null as its output state for ant input.
Finally, we have the DFA for the given NFA.

Explanation

Given transition table for NFA

	a	b	ε
1	{2,5}	{1,3}	{}
2	{2}	{3}	{4}
3	{5}	{}	{}
4	{}	{4}	{3}
5*	{}	{}	{}

Q={1,2,3,4,5}, {a,b,ε}, F={5}

 

 

DFA Construction

1] Q1=Φ

2] Q1={1}

3] For each state in Q1, find states for each input symbol.

4] Now on getting new state, find transitions for them.

DFA State transition table

	a	b	ε
1	{2,5}	{1,3}	Φ
{2,5}	{2}	{3}	{4}
{1,3}	{2,5}	{1,3,4}	{3}
{2}	{2}	{3}	{4}
{3}	{5}	Φ	Φ
{4}	{}	{4}	{3}
{1,3,4}	{2,5}	{1,3,4}	{3}
5*	Φ	Φ	Φ
Φ	Φ	Φ	Φ

 

 

 

 

Q={1,{2,5},{1,3},2,3,4,5,{1,3,4}, Φ}

ε={a,b,ε}

F={5,{2,5}}

initial state =1

 

Also read, Draw the memory map of the following code and write the output of the program.