edited by
2,323 views

4 Answers

Best answer
36 votes
36 votes
  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$

edited by
4 votes
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)*.
1 votes
1 votes

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.

1 votes
1 votes
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.
Answer:

Related questions

20 votes
20 votes
8 answers
4
makhdoom ghaya asked Dec 5, 2015
3,046 views
A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \time...