Question 26
A Context-Free Grammar (CFG) is defined as a 4-tuple $G = (V$, T, P, S). What constraint is placed on production rules in P?
In CFG, every rule LHS consists strictly of a single non-terminal symbol A without surrounding context.
A Context-Free Grammar (CFG) is defined as a 4-tuple $G = (V$, T, P, S). What constraint is placed on production rules in P?
In CFG, every rule LHS consists strictly of a single non-terminal symbol A without surrounding context.
A grammar that produces more than one distinct parse tree for the exact same input sentence is called -
Grammars that yield multiple parse trees (or multiple leftmost derivations) for a single string are termed ambiguous.
A Context-Free Grammar is unambiguous if and only if every valid sentence in the language has -
Unambiguity guarantees a 1-to-1 mapping between valid input strings and their leftmost derivation parse trees.
What language is generated by the Context-Free Grammar S → 0S1 | 1S0 | SS | $\epsilon$?
S → 0S1 and S → 1S0 generate balanced pairs of 0s and 1s in any order, producing all strings with equal 0 and 1 counts.
A Context-Free Grammar is in Chomsky Normal Form (CNF) if every production rule is of the form -
CNF restricts production RHS to either exactly two non-terminals (A → BC) or a single terminal symbol (A → a).