Question

Let r =1 $(1+0{)}^{\ast },s={11}^{\ast }0andt=1^{\ast }0$ be three regular expressions. which one of the following is true?

• A. $L\left(s\right)\subseteq L\left(r\right)andL\left(s\right)\subseteq L\left(t\right)$
• B. $L\left(s\right)\subseteq L\left(t\right)andL\left(s\right)\subseteq L\left(r\right)$
• C. $L\left(r\right)\subseteq L\left(s\right)andL\left(s\right)\subseteq L\left(t\right)$
• D. $L\left(t\right)\subseteq L\left(s\right)andL\left(s\right)\subseteq L\left(r\right)$

Answer 1

Answer: (A), (B)

$L\left(s\right)\subseteq L\left(t\right)andL\left(s\right)\subseteq L\left(r\right)$

$r=1(1+0{)}^{\ast }$

So the language corresponds to r is all strings starting with 1.

$S={11}^{\ast }0$

The language corresponding to s is all strings starting with 1 followed by any number of 1 and end with 0. So s has more resitrictions as compared to r.

So, $L\left(s\right)\subseteq L\left(r\right)$

$t=1^{\ast }0$

The language corresponding to t is all strings ending with 0. Since s has to start with atleast one 1 but t can start with zero 1s. So s has more restriction compared to t.

So, $L\left(s\right)\subseteq L\left(t\right)$

Note: Choices (a) and (c) are actually same.