Computation and Regular Expressions - Find a regular expression for the following scenarios

Question

Find regular expressions for:

• A. All binary strings with exactly two $1’s$

• B. The set $\{a^nb^m :n\geq3, m$ is even$\}$

• C. All binary strings with a double symbol (contains $00$ or $11$) somewhere.

• D. The language on $\Sigma=\{a,b\}, L=\{w:n_a(w) \mod 3=0\}$

Answer 1

$1.L_{1}=0^{*}10^{*}10^{*}$

---

$2.L_{2}=aaaa^{*}\left ( bb \right )^{*}$

---

$3.L_{3}=\left ( 0+1 \right )^{*}00\left ( 0+1 \right )^{*}+\left ( 0+1 \right )^{*}11\left ( 0+1 \right )^{*}$

---

$4.L_{4}=b^{*}(ab^{*}ab^{*}ab^{*})^{*}$

Comments

For $L_4$, b is not accepted.

---

sir $L_{4}=(b^{*}ab^{*}ab^{*}ab^{*})^{+}?$

---

can we write L1 as (110* + 0*110*+ 0*10*1+10*10*) ? 

I know L1=0*10*10*  covers it , but still is above is also correct?

---

No, that also won't accept b rt? We should allow no a's because 0 is divisible by 3.

---

Sir , i am not getting you .

If you are saying that my $L_{4}$ should accept $b$,then my $L_{4}$ is actually accepting $b$

$L_{4}=b^{1}(b^{*}ab^{*}ab^{*}ab^{*})^{0}b^{0}$

 

Actually i too though that $n(a)=0$ should be accpeted as 0 is divisible by 3

---

yes, sorry I missed that. But you can avoid b* at end.

---

okk sir , thank you :)

---

thank you Sir

---

for L4 why not   b*(ab*ab*ab*)*   ?

---

@diksha , yes you are correct.Thanks

---

L4 can also be expressed as (b + ab*ab*a)*

Answer 2

solution

Ans1.   0*10*10*

Answer 3

.........