in Theory of Computation retagged by
184 views
0 votes
0 votes

Please explain your Answer

in Theory of Computation retagged by
184 views

1 comment

If it is a msq then add msq tag
0
0

1 Answer

3 votes
3 votes
Best answer
(a) $R_1=(0^*1 + 1^*0)^*0 + 11^*0^*$

Here, $(0^*1+1^*0)$ can generate $1,0 \implies (0^*1+1^*0)^*$ can generate all strings ie it is equivalent to $(0+1)^*$.

$R_1 \equiv (0+1)^*0+ 1^+0^*$

Here, $(0+1)^*0$ covers every string ending with $0$, so we can say every string that belongs to $1^+0^*$ and ends with $0$ is already accounted for. So, we can reduce it to $1^+$.

$R_1 \equiv (0+1)^*0 + 1^+ = R_2$

Therefore, both regular expressions are equivalent in (a).

(b) $((0+1)(0+1))^*$ can generate $1101$ but the other regular expression cannot.

Therefore, both regular expressions are not equivalent in (b).

(c) $(10+001+0^*1^*)^+$ can generate $\epsilon$ but the other regular expression cannot.

Therefore, both regular expressions are not equivalent in (c).

(d) $R_2 = (0+1)^*(\phi^+ +\epsilon) \equiv (0+1)^*$

$R_1 = (00^*1^* + 1^*10^*)^*(\phi ^* + \phi) \equiv (00^*1^*+1^*10^*)^*(\epsilon + \phi)$

Here, $(00^*1^* + 1^*10^*)$ can generate $0,1 \implies (00^*1^*+1^*10^*)^*$ can generate all strings ie it is equivalent to $(0+1)^*$.

$R_1 \equiv (0+1)^*(\epsilon + \phi) \equiv (0+1)^*$

Therefore, both regular expressions are equivalent in (d).
selected by