Peter Linz-Chapter 3.1 Regular Expressions

Question

Give a regular expression  for the language over {0,1}

NOT CONTAINING 101 AS SUBSTRING.

Answer 1

Containing $101$ as a substring.

 

Not containing $101$ as substring.

 

To find the regular expression for above DFA, we remove trap state.

Now using Arden's theorems:

$\begin{align*} &A = \epsilon + A0 + C0 \quad \dots (1) \\ &B = A1 + B1 \quad \dots (2)\\ &C = B0 \quad \dots (3)\\ \\ \hline \\ &\Rightarrow \text{substitute C in (1)} \\ &A = \epsilon + A0 + B00 \quad \dots (4) \\ &(2) \Rightarrow B = A11^{*} \\ &\text{Now , substitute this B value in (4)} \\ &A = \epsilon + A0 + A11^{*}00 \quad \dots (4) \\ &\Rightarrow A = \epsilon + A\left ( 0 + 11^{*}00 \right ) \\ &\Rightarrow A = \left ( 0 + 11^{*}00 \right )^{*} \\ &\Rightarrow B = \left ( 0 + 11^{*}00 \right )^{*}11^{*} \qquad \text{using (2)} \\ &\Rightarrow C = \left ( 0 + 11^{*}00 \right )^{*}11^{*}0 \qquad \text{using (3)} \\ &\Rightarrow \text{Regular Exp} = A + B + C = \left ( 0 + 11^{*}00 \right )^{*}\left ( \epsilon + 11^{*} + 11^{*}0 \right ) \\ \end{align*}$

Comments

For multiple choice question of this kind, we need not do all these, then we should eliminate options and select the correct one !

---

Thanks debashish. Solution was absolutely clear. Also got to know about Arden's theorem in a greater clarity.

---

thanks dude