A Context-Free Grammar is in Greibach Normal Form (GNF) if every production rule is of the form -
GNF mandates that every production RHS begins with exactly one terminal followed by a string of non-terminals.
If a CFG is in Chomsky Normal Form (CNF), how many derivation steps are required to derive a string of length n (n $\ge 1$)?
In CNF, deriving a string of length n requires (n - 1) binary non-terminal expansions A → BC plus n terminal replacements A → a, totaling 2n - 1 steps.
What is the minimum number of productions required to generate all palindrome strings over alphabet $\Sigma = {a, b}$?
Generating palindromes over {a, b} requires 5 rules: S → aSa | bSb (even length extensions), S → a | b (odd length bases), and S → $\epsilon (even length base)$.
Which of the following operations is Context-Free Languages (CFL) NOT closed under?
CFLs are closed under Union, Concatenation, and Kleene Star, but are NOT closed under Intersection or Complement.
Is the Intersection of a Context-Free Language (CFL) and a Regular Language guaranteed to be Context-Free?
While CFLs are not closed under general intersection, the intersection of a CFL with a Regular Language is always Context-Free (proved via product automaton of PDA and DFA).