The Gateway to Computer Science Excellence
+17 votes

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.
in Theory of Computation by Boss (30.8k points)
edited by | 619 views

4 Answers

+32 votes
Best answer
  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\}$
  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 by
nice... explanation
+4 votes
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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,909 users