GATE CSE 2004 | Question: 8

Question

Which of the following grammar rules violate the requirements of an operator grammar? $P, Q, R$ are nonterminals, and $r, s, t$ are terminals.

1. $P \rightarrow Q R$

2. $P \rightarrow Q s R$

3. $P \rightarrow \: \varepsilon$

4. $P \rightarrow Q t R r $

• A. (I) only
• B. (I) and (III) only
• C. (II) and (III) only
• D. (III) and (IV) only

Comments

ans-B

---

An operator precedence grammar is a context-free grammar that has the property that no production has either an empty right-hand side or two adjacent non terminals in its right-hand side.

Hence answer is B.

Ref: https://en.wikipedia.org/wiki/Operator-precedence_grammar

---

An operator grammar *cannot* have 2 things:

   1) Two Adjacent NonTerminals, &

   2) An null value

Answer 1

answer is B.

Operator grammar  cannot contain  

1. Nullable variable  
2. Two adjacent non-terminal on $\text{RHS}$ of production

Comments

Please explain option IV

P->QtRr

---

$P \rightarrow$ variable terminal variable terminal

i.e, NO two consecutiver varibale/ Non-terminals; Hence no violation

Answer 2

(I) P --> QR is not possible since two Non Terminal  should include one operator as Terminal.
(II) Correct
(III)  incorrect.
(IV) Correct.

so I and III violate the requirements of an operator grammar.

Hence (B) is correct option

Comments

is PQ-->RsT is operator grammar or not?

---

no, PQ-->RsT will also not be in operator grammer, because

PQ is present in LHS means it has also been generated by some production like V ---> αPQβ which is also in grammer and voilating operator precedence condition..

---

No, PQ-> RsT is not context free, so it cant be operator grammar.

---

@joshi+nitish

Not able to understand ur above comment ..

is this right reasoning

PQ -> Rst ...is not CFG hence not Operator Grammar /?

Answer 3

A grammar is an Operator Grammar if and only if its productions satisfy two mandatory conditions:

1. No $\epsilon$-productions: No production has an empty right-hand side ($A \rightarrow \epsilon$).

2. No adjacent non-terminals: No two non-terminals appear side-by-side on the right-hand side (e.g., $A \rightarrow \dots BC \dots$ is forbidden).

Rules (I) and (III) violate the requirements.

B. (I) and (III) only