Home › GATE CSE › computerscience › Theory of Computation › A CONTEXT-FREE GRAMMAR (CFG) is a 4-tuple $G = (…
A CONTEXT-FREE GRAMMAR (CFG) is a 4-tuple $G = (V, \Sigma, R, S)$. What does $R$ represent?
Athe set of variables (non-terminals)
Bthe input alphabet
Cthe set of production rules of the form $A \to \alpha$
Dthe start symbol
Answer & Solution
Correct answer: C. the set of production rules of the form $A \to \alpha$
1. A CFG consists of:
- $V$: finite set of VARIABLES (non-terminals, capital letters by convention)
- $\Sigma$: finite set of TERMINALS (the alphabet)
- $R$: finite set of PRODUCTION RULES of form $A \to \alpha$ where $A \in V$ and $\alpha \in (V \cup \Sigma)^*$
- $S \in V$: the START symbol
2. Each rule allows one variable to be replaced by a string of variables and terminals.
3. Generation: starting from $S$, apply rules to derive a string of terminals (which is in the language $L(G)$).
4. Other options name different tuple components.
_Source: Jeff Erickson, "Models of Computation", §5.1 (Context-Free Grammars — tuple definition)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?