Theory of Automata - Assignments

Q. 1.                                                                                                    Marks [10]

Suppose we have a Transition Graph (TG) as follows:

Derive regular expression for the above transition graph. Briefly explain each and every step.

 

Answer:

According to Kleenes’ theorem part II, step 1 introduces new start state connected with the old start states through NULL transitions as follows:

In step 2, new final state is introduced connected with both final states through NULL transitions as follows:

 

Step 3 replaces multiple incoming transition edges by a single transition labeled by the corresponding regular expression as follows:

 

In step 4, loops are eliminated as follows:

 

After applying step 4 to eleminate and bypass states we get:

 

Finally applying step 4 once again we get:

 

Q. 2.                                                                                                    Marks [10]

Develop a Finite Automaton (FA) corresponding to the union of above two FAs.

Answer:

Old states	New states after reading
	a	b
Z1- = (X1,Y1)	(X2,Y1) = Z2	(X2,Y2) = Z3
Z2 = (X2,Y1)	(X3,Y1) = Z4	(X3,Y2) = Z5
Z3 = (X2,Y2)	(X3,Y3) = Z6	(X3,Y2) = Z5
Z4 = (X3,Y1)	(X4,Y1) = Z7	(X3,Y2) = Z5
Z5 = (X3,Y2)	(X4,Y3) = Z8	(X3,Y2) = Z5
Z6+ = (X3,Y3)	(X4,Y3) = Z8	(X3,Y2) = Z5
Z7+ = (X4,Y1)	(X4,Y1) = Z7	(X4,Y2) = Z9
Z8+ = (X4,Y3)	(X4,Y3) = Z8	(X4,Y2) = Z9
Z9+ = (X4,Y2)	(X4,Y3) = Z8	(X4,Y2) = Z9