Which of the following grammars are operator grammars? Here E, F, and T are…
2021
Which of the following grammars are operator grammars? Here E, F, and T are non-terminals; +, *, i, and d are terminal symbols; and ε denotes the empty string.
G₁: E → E+T | T; T → T*F | F; F → i | d
G₂: E → E+T | T; T → T*F | F; F → i | d | ε
G₃: E → E+T | T; T → T*F | F | ε; F → i | d
G₄: E → E+T | T; T → F; F → i | d | F*i | ε
Answer: D. None of these — CONCEPTAn operator grammar is a context-free grammar whose productions have neither ε on the right-hand side nor two adjacent non-terminals on the right-hand…
- A.
G₁, G₂
- B.
G₁, G₃, G₅
- C.
G₁, G₃, G₄
- D.
None of these
Attempted by 236 students.
Show answer & explanation
Correct answer: D
CONCEPT
An operator grammar is a context-free grammar whose productions have neither ε on the right-hand side nor two adjacent non-terminals on the right-hand side.
These restrictions make precedence relations between terminals well-defined; unit productions such as E → T or T → F do not violate either restriction.
APPLICATION
G₁ has no ε-production, and operators separate the non-terminals in E → E+T and T → T*F. Its remaining right-hand sides contain single non-terminals or terminals, so G₁ passes both checks.
G₂ contains F → ε, so it fails the no-ε restriction.
G₃ contains T → ε, so it fails the no-ε restriction.
G₄ contains F → ε, so it fails the no-ε restriction; the production F → F*i itself has its non-terminal and terminal separated by *.
CROSS-CHECK / CONTRAST
G₁, G₂ includes G₂, which has F → ε.
G₁, G₃, G₅ includes G₃ with T → ε and also refers to G₅, which is not defined in the stem.
G₁, G₃, G₄ includes two grammars with ε-productions.
Only G₁ survives both structural checks, and no explicit list contains G₁ alone.
Therefore the matching offered value is “None of these”.