Lecture 9 (Computation Theory) Context-Free Grammars and Pushdown Automata

A context-free grammar is defined as a 4-tuple (V, Sigma, R, S). What does the rule format A -> alpha require of the left- and right-hand sides?

1. A.A is a single variable; alpha is any string of variables and terminals
2. B.A is any string of terminals; alpha is a single variable
3. C.Both A and alpha must be single terminals
4. D.A and alpha must be strings of equal length