recategorized by
1,602 views
3 votes
3 votes

Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively.

Which of the following is true with respect to the two languages?

  1. $L_1 \subset L_2$
  2. $L_2 \subset L_1$
  3. $L_1 = L_2$
  4. $L_1 \cap L_2 = \phi$
recategorized by

5 Answers

1 votes
1 votes
L1= (a* +b) *  can give every string over a,b

L2= (a+b) * can give every string over a,b

so both are same

option C
0 votes
0 votes
C. L1=L2

Because

language generated by (a*+b) * = language generated by (a+b) *
0 votes
0 votes
$L1 = (a^*+b)^*$ accepts all strings that have any number of a’s and any number of b’s.

$L2 = (a + b)^*$ also does the same.

The extra * over a in the first language is redundant as the language L1 would anyway contain strings with all possible combinations of a and b.

Thus, the two languages are one and the same.

In fact, $(a+b)^* = (a^*+b^*)^* = (a^*+b)^* = (a+b^*)^*$

All of these languages are equivalent to each other.

Clearly, $L1 = L2$.

$\therefore$ Option C is correct.
edited by
Answer:

Related questions

2 votes
2 votes
2 answers
1
go_editor asked Nov 20, 2020
1,543 views
Consider the following regular expressions:$r=a(b+a)^*$$s=a(a+b)^*$$t=aa^*b$Choose the correct answer from the options given below based on the relation between the langu...