a) Consider the two regular expressions $R1 = a^+b^ \quad R2 = ab^*…

Previous year question for Theory of Computation.

Question

a) Consider the two regular expressions

$R1 = a^*+b^* \quad R2 = ab^*+ab^*+b^*a+(a^*b)^*$.

i) Find a string corresponding to R1 but not R2.

ii) Find a string corresponding to R2 but not R1.

iii) Find a string corresponding to both R1 and R2.

b) Construct a DFA equivalent to NFA.

| State | 0 | 1 | 2 |

|---|---|---|---|

| $\rightarrow q_0$ | $\{q_1,q_4\}$ | $q_4$ | $\{2,q_3\}$ |

| $q_1$ | $-$ | $q_4$ | $-$ |

| $q_2$ | $-$ | $-$ | $\{q_2,q_3\}$ |

| $q_3$ | $-$ | $q_4$ | $-$ |

| $q_4$ | $-$ | $-$ | $-$ |