0
$\begingroup$

The options are:

(a) $L \cap a^{\ast}b^{\ast}$

(b) $(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$

(c) $L \cup a^{\ast}b^{\ast}$

(d) $(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$

My doubt is: We don't know what exactly $L$ is, it could be $a^{n}b^{n}$ or $b^{n}a^{n}$, we for sure know that $L$ is either of the two!

The way I think is, when we look at the first option the resultant language can be either $\epsilon$ or $a^{n}b^{n}$ because $L$ can be either of the mentioned choices, which also means that we can't deduce it properly, similarly i cannot decipher the other options.

Can someone explain why each option is either correct or wrong choice? Given that the correct option is $(b)$

$\endgroup$
2
  • $\begingroup$ "We don't know what exactly L is, it could be $a^nb^n$ or $b^na^n$, we for sure know that L is either of the two!" > I don't understand this sentence. $a^nb^n$ and $b^na^n$ are words, not languages. And even if you meant $\{a^nb^n\mid n\geqslant 0\}$, this is not equal to $L$. $L$ contains all words with the same number of $a$'s and $b$'s, like $a^nb^n$ for any $n$, but also $b^na^n$, but also $abababab…$, but also $aabbbbaa$, … $\endgroup$
    – Nathaniel
    Commented Apr 8, 2023 at 10:14
  • $\begingroup$ @Nathaniel Oh that's true! I did think of that but somehow convinced myself otherwise but now that you have re-stated it in a clear format, i agree $L$ can be any of the langauges you mentioned. And yes i meant langauges as you said! Do you know how to further deduce the solution? $\endgroup$ Commented Apr 8, 2023 at 10:23

1 Answer 1

1
$\begingroup$

(b) is the only correct answer and this follows directly from the well known proof, $L_1 = \{a^n b^n : n \in \mathbf{N}\}$ is not regular. You can refer to the second page of this resource, for example.


(a) We start of by noting that $L' = L \cap a^*b^*$ is equivalent to $L_1$, which is not regular.

(b) $L_1 \cup a^*b^*$ is equivalent to $a^*b^*$ which is regular. This can be easily verified by constructing a single state automaton accepting any number of $a$s and $b$s.

(c) We prove this using pumping lemma. Let $x = b^na^n$. Clearly, $x \in L', |x| \geq n$.
Let $uv = b^j$ for some $j \in \mathbf{N}, 0 \leq j \leq n, v = b^k$ for some $k \in \mathbf{N}, 0 < k \leq n$.
If $L'$ was regular, then $uv^2w = b^{n+k}a^n \in L'$, which is not true. Thus, $L'$ is not regular.

(d) Here, $L' = a^nb^n \cup b^*a^*$. Apply the same proof as in (c) for the string $x = a^kb^k, k \in \mathbf{N}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.