Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11

Question

A.    [(00(0+1)* 11] + [11( 0 + 1)* 00]
B.    [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)].
C.    [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
D.    (00+11) (0+1)* (00+11).

Answer 1

The correct answer would be C.

The regular expression can be categorized into two subparts.
$R= L_1 + L_2 $
$L_1$ = The strings which begin with $00$ or $11$.
$L_2$ = The strings which end with $00$ or $11$.
Let us find out $L_1$ and $L_2$.
$L_1$ = $(00 + 11)$ .  (any number of 0's and 1's )
$L_1$ = $(00 + 11). {(0+1)}^{*}$
Similarly $L_2$ = (any number of 0's and 1's ) . $( 00 + 11)$ = ${(0+1)}^{*} (00 + 11) $
Hence R= $[(00+11) {(0+1)}^{*}] + [{( 0 + 1)}^{*} (00+11)]$.

Comments

why option D is not correct (00+11) (0+1)* (00+11). it is also going to start with either 00 or 11 and ends with either 00 or 11.

---

Sir that will not accept strings like 00,11.

Answer 2

Ans C)
  [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]

here either start with 00 or 11 , then minimum string will be 00 or 11

if end with 00 or 11 the also minimum string is 00 or 11

Here ⋋ also accepted, but that is not mentioned in any option

Comments

@Deep99 Option (d) is a regular expression which denotes a Language which accept all the string which begin "and " end with 00 and 11  

---

Option d is not correct b/c minimum string accepted by regular expression is 00 or 11...that is not fullfill by option d..

---

Counter case for D) is it does not generate string 0010 which is correct as per given question because it is starting with 00 and it doesn't matter that it should be end with either 00 or 11.

But from option C) we can do that.

Hope this Helps readers.