Question 31
Are Context-Free Languages closed under Set Difference (L1 - L2)?
Since $\Sigma *$ is regular and CFLs are not closed under complement, set difference L1 - L2 = L1 ∩ L2' is not closed for general CFLs.
Are Context-Free Languages closed under Set Difference (L1 - L2)?
Since $\Sigma *$ is regular and CFLs are not closed under complement, set difference L1 - L2 = L1 ∩ L2' is not closed for general CFLs.
If L1 is a Context-Free Language and L2 is a Regular Language, is their Set Difference (L1 - L2) Context-Free?
L1 - L2 = L1 ∩ L2'; since Regular languages are closed under complement, L2' is regular. The intersection of a CFL with a Regular Language is context-free.
Which decision problem is UNDECIDABLE for Context-Free Grammars?
Testing whether an arbitrary CFG is ambiguous is a well-known undecidable decision problem (reducible from Post Correspondence Problem).
Is the Universality Problem ('Is L(G) = $\Sigma *$ for a given CFG G?') Decidable or Undecidable?
Determining whether a CFG generates all possible strings $\Sigma *$ is undecidable.
What is the language generated by the grammar S → aSB | ab, B → b?
S → aSB derives $a^k$ S $B^k$; replacing S with 'ab' yields $a^k$ ab b^$k = a^{k+1} b^{k+1} = a^n b^n$ for $n = k + 1 \ge 1$.