Given the nondeterministic finite state machine shown below

Given the nondeterministic finite state machine shown below, find its nondeterministic equivalent. The input to the machine are the symbols a and b. The states of the machine are 1, 2, and 3. You must use the algorithm for converting a NDFSM to a DFSM. Once you have finished transforming the machine to a DFSM, find the regular grammar associated with this machine.

Solution

Algorithm

The states which contain any of the final states of the NDFSM are the final states of the equivalent DFSM.

Table already given for the NDFSM

DFA Table some server issues unable to upload image using table construct the state machine fig

grammar it accepts are a,ab,abab,aaa,aba, etc

Input:	An NDFSM
Output:	equivalent DFSM
Step 1	Create state table from the given NDFSM.
Step 2	Create a blank state table under possible input alphabets for the equivalent DFSM.
Step 3	Mark the start state of the DFSM by q0 (Same as the NDFSM).
Step 4	Find out the combination of States {Q0, Q1,... , Qn} for each possible input alphabet.
Step 5	Each time we generate a new DFSM state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.
Step 6	The states which contain any of the final states of the NDFSM are the final states of the equivalent DFSM. Table already given for the NDFSM DFA Table some server issues unable to upload image using table construct the state machine fig state a b FS 1 2,3 2 yes bcz of 3 2,3 1 1,3 yes bcz of 3 2 1 no 1,3 2,3 2,3 yes bcz of 3 3 1 3 yes grammar it accepts are a,ab,abab,aaa,aba, etc