recategorized by
642 views
1 votes
1 votes

For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the following sentences.

  1. $\overline{L}$ and $L^{\ast}$ are both context-free.
  2. $\overline{L}$ is not context-free but $L^{\ast}$ is context-free.
  3. $\overline{L}$ is context-free but $L^{\ast}$ is regular.

Which of the above sentence(s) is/are true if $L=\left \{ a^{n}b^{n} \mid n\geq 0\right \}$?

  1. Both (i) and (iii)
  2. Only (i)
  3. Only (iii)
  4. Only (ii)
  5. None of the above
recategorized by

1 Answer

0 votes
0 votes
Option $(B)$

$\bar{L} = \{a^nb^m|n \neq m ;n,m \geq 0\}$ This is CFL

$L^{*} = (a^nb^n)^*$ will always be CFL as CFL are closed under kleene-closure but it is not regular as it requires $b$ to match with the $a$ before starting with another runs of $a$.
edited by
Answer:

Related questions

2 votes
2 votes
1 answer
1
soujanyareddy13 asked Mar 25, 2021
462 views
Consider the following two languages.$\begin{array}{rcl} \text{PRIME} & = & \{ 1^{n} \mid n \text{ is a prime number} \}, \\ \text{FACTOR} & = & \{ 1^{n}0 1^{a} 01^{b} ...
1 votes
1 votes
2 answers
2
soujanyareddy13 asked Mar 25, 2021
566 views
Which of the following regular expressions defines a language that is different from the other choices?$b^{\ast }\left ( a+b \right )^\ast a\left ( a+b \right )^ \ast ab^...