3 votes 3 votes Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free languages is never regular The subset of a decidable language is always decidable 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? Only $(1)$ Only $(1)$ and $(2)$ Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true. Theory of Computation tifr2020 theory-of-computation context-free-language decidability + – admin asked Feb 10, 2020 edited Apr 12, 2020 by go_editor admin 1.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Ashwani Kumar 2 answered Feb 11, 2020 Ashwani Kumar 2 comment Share Follow See all 0 reply Please log in or register to add a comment.
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. smsubham answered Mar 6, 2020 smsubham comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option e) None of the above is correct. Sanandan answered Oct 3, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Option E is correct rish1602 answered Jan 15, 2022 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.