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 |
