Redirected
edited by
1,342 views

2 Answers

Best answer
13 votes
13 votes

AR is all stings over {a,b} that contain "ba" as substring.i.e, (a+b)*ba(a+b)*

B is all strings over {a,b} that doesn't contain "ba" as substring ,i.e, a*b*

so AR + B = (a+b)* = C 

Option C is  correct. 

NFA for A and its equivalent DFA.


Reversal of A , that is resulting in NFA

Equivalent DFA for AR is 

selected by
6 votes
6 votes

$$\begin{array}{ll|l}
A &= (a+b)^*\;ab\;(a+b)^* & \text{Strings containing substring } ``ab"\\[1em]
A^R &= (a+b)^*\;ba\;(a+b)^* & \text{Strings containing substring } ``ba"\\[2em]
B &= a^*b^* & \text{All $a$'s should come before any $b$'s}\\[1em]
B^R &= b^*a^* & \text{All $b$'s should come before any $a$'s}\\[2em]
C &= (a+b)^* & \text{All strings}
\end{array}$$

Now,

$A+B$ doesn't give us all the strings. For example, $A+B$ doesn't contain the string $``ba"$.

Thus, $A+B \neq C$


$A^R+B^R$ doesn't give us all the strings. For example, $A^R+B^R$ doesn't contain the string $``ab"$.

Thus, $A^R+B^R \neq C$


$A^R+B$ does give us all the strings!

First, lets look at which strings don't come in $B$. They are the ones that contain atleast one such $``a"$ that occurs after some $``b"$. For example, $B$ doesn't contain the string $``aba"$

Now, we observe that all the strings that do not come in $B$, satisfy the property for $A^R$, and hence come in $A^R$.

Thus, if we union $A^R$ and $B$, we will get all strings.

Hence, $A^R + B = C$

Another way to verify it is by constructing an NFA for $A^R + B$, converting it to DFA and minimizing it.

Related questions

2 votes
2 votes
2 answers
1
Mojo-Jojo asked Sep 28, 2015
1,128 views
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ?Does this imply that a subset of non regular language can be regular ?
2 votes
2 votes
2 answers
4
techbrk3 asked Nov 2, 2017
10,626 views
a) Reflexive. Transitive but not Symmetricb) Reflexive. Symmetric but not Transitivec) Symmetric, Transitive but not Reflexived) An equivalence relation