edited by
1,501 views
3 votes
3 votes

Consider the following statements.

  1. The intersection of two context-free languages is always context-free
  2. The super-set of a context-free languages is never regular
  3. The subset of a decidable language is always decidable
  4. Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of all strings in which either the number of occurrences of $a$ is the same as the number of occurrences of $b$ OR the number occurrences of $b$ is the same as the number of occurrences of $c$. Then, $L$ is not context-free.

Which of the above statements are true?

  1. Only $(1)$
  2. Only $(1)$ and $(2)$
  3. Only $(1),(2)$ and $(3)$
  4. Only $(4)$
  5. None of $(1),(2),(3),(4)$ are true.
edited by

4 Answers

2 votes
2 votes

$1)$ CFL is not closed under intersection.

$2)$ $\sum^*$ is the superset of every CFL which is regular

$3)$ Not true

$4)$ It is non deterministic CFL.

Option e) is correct answer

0 votes
0 votes

1. CFL not closed under intersection.

https://cs.stackexchange.com/questions/91321/why-are-cfls-not-closed-under-intersection

2. False. L is equal number of a and b. L2 (Superset of this is) sigma*, which is regular.

3. False.

https://cs.stackexchange.com/questions/17966/is-every-subset-of-a-decidable-set-also-decidable

4. False. L = {$ a^mb^nc^k$, $m=n$ or $n=k$}

So E is correct.

Answer:

Related questions

3 votes
3 votes
1 answer
3