Question 81
Which statement about CFG equivalence is correct?
Detailed Solution
No algorithm decides equivalence of all pairs of CFGs.
✓ Saved
GATE CSE Context-Free Languages, Grammars & Pushdown Automata – TOC Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 82
Which operations preserve context-freeness for a CFL L?
Detailed Solution
CFLs are closed under reversal, star, and concatenation, but not complement.
✓ Saved
Question 83
A parse tree of a CNF grammar deriving a nonempty string of length n has how many internal binary nodes?
Detailed Solution
A full binary tree with n terminal leaves has n-1 internal binary nodes.
✓ Saved
Question 84
Which statements about CNF parse trees for a nonempty string of length n are correct?
Detailed Solution
A full binary tree with n leaves has n-1 internal nodes; CNF gives n terminal and n-1 binary applications.
✓ Saved
Question 85
In a CNF derivation of a nonempty string of length n, how many total production applications occur in the parse tree?
Detailed Solution
There are n terminal productions and n-1 binary productions.
✓ Saved