Skip to content
GATETECH
Official PYQ · 2014Set 2 · Q39Syntax-directed TranslationNAT1 mark

GATE CS 2014 Set 2 Q39 — Syntax-directed Translation

Explain with AI

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 00 or 11. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. 

View worked solution

Answer: 6

The given expression tree represents the following algebraic expression:

E=[(x1+x2)×(x3+x4)]−[x5−(x6+x7)]E = [(x_1 + x_2) \times (x_3 + x_4)] - [x_5 - (x_6 + x_7)]

where each leaf variable xi∈{0,1}x_i \in \{0, 1\}. To maximize the overall value of EE, we must maximize the left subtree and minimize the right subtree of the root subtraction operator:

  1. Maximize the left subtree: L=(x1+x2)×(x3+x4)L = (x_1 + x_2) \times (x_3 + x_4) Setting x1=x2=x3=x4=1x_1 = x_2 = x_3 = x_4 = 1 gives the maximum value: Lmax=(1+1)×(1+1)=4L_{\text{max}} = (1 + 1) \times (1 + 1) = 4
  2. Minimize the right subtree: R=x5−(x6+x7)R = x_5 - (x_6 + x_7) Setting x5=0x_5 = 0 and x6=x7=1x_6 = x_7 = 1 gives the minimum value: Rmin=0−(1+1)=−2R_{\text{min}} = 0 - (1 + 1) = -2

Substituting these values back into the main expression:

Emax=Lmax−Rmin=4−(−2)=6E_{\text{max}} = L_{\text{max}} - R_{\text{min}} = 4 - (-2) = 6

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Syntax-directed Translation questions