619 views

Let $a, b, c$ be regular expressions. Which of the following identities is correct?

1. $(a + b)^{*} = a^{*}b^{*}$
2. $a(b + c) = ab + c$
3. $(a + b)^{*} = a^{*} + b^{*}$
4. $(ab + a)^{*}a = a(ba + a)^{*}$
5. None of the above.

edited | 619 views

1. $(a+b)^* = \{$ any strings of over $\{a,b\} \}$
$a^*b^* = \{$ any number of $a$'s followed by any number of $b$'s $\}$
False, as strings, $ba , aba, bab$, etc are not present in $a^*b^*$
2. $a(b+c)= \{ab,ac\}$
$ab+c= \{ab,c\}$
False
3. $(a+b)^* = \{$ any strings of over $\{a,b\} \}$
$a^*+b^* = \{$ any numbers of $a$'s or any numbers of $b$'s $\}$
False , as strings , $ab, ba, aba, bab$ etc are not present in $a^*+b^*$
4. $(ab+a)^*a = a(ba+a)^*$ , True
$\\p(qp)^* =p\{\epsilon ,qp,qpqp,qpqpqp,...\}\\=\{p,pqp,pqpqp,pqpqpqp,...\}\\=\{\epsilon ,pq,pqpq,pqpqpq,...\}p\\=(pq)^*p$
$(ab+a)^*a=(a(b+\epsilon ))^*a=a((b+\epsilon)a)^* =a(ba+a)^*$

Correct Answer: $D$

by Veteran (57k points)
edited
0
nice... explanation
Ans will be (D)

Because (D) is consisting of strings which are start with 'a' and end with 'a' . Minimum string for this language is 'a' and also atleast one 'a' with each 'b' so that no two b comes together. Each string also have atleast one 'a' greater than number of b it has.

So, the strings that accepted by the language {a,aa,aba, ababa..............} which is accepted by both left side (ab+a)*a and also right side a(ba+a)*.
by Veteran (119k points)
+1 vote

a. not contain ba string in rhs

b. not contain ac string in rhs

c. RHS contain only string containing no of a's or no of b's only

Above all are not equal.

d. It is correct because LHS string of ab or a ending with a is equivalent to a followed by ba or a. Both Regular expression produce palindrone of odd length start or end with a  and another string containing any no of a's string.

by Active (3.1k points)
+1 vote
a. This is wrong. RHS can only generate strings in which b is followed by a  or an empty string while in LHS this is not the restriction.
b. This is wrong. Eg. LHS could generate ac while RHS cannot.
c. This is wrong. Kind of similar with option a.
d. This seems to be True. We can generate all the strings in RHS that can be generated by LHS.
by Loyal (9.5k points)