Log In
18 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
edited by

4 Answers

35 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$

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)*.
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.

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.

Related questions

13 votes
3 answers
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic finite state automaton ... but not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1.1k views
17 votes
7 answers
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 \times 8$ chessboard? $64$ $65$ $204$ $144$ $256$
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.4k views
20 votes
2 answers
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the following is true? $L_{1}$ ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
asked Dec 8, 2015 in Theory of Computation makhdoom ghaya 1.3k views
23 votes
5 answers
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the set of languages ... countably infinite. $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 2.1k views