2.2k views

Match the following:

 E. Checking that identifiers are declared before their use P. $L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$ F. Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function Q. $X\: \rightarrow XbX \mid XcX \mid dXf \mid g$ G. Arithmetic expressions with matched pairs of parentheses R. $L\: = \left\{wcw\mid w \: \in \left(a\mid b\right)^* \right\}$ H. Palindromes S. $X \: \rightarrow \: bXb \mid \:cXc \: \mid \epsilon$

1. E-P, F-R, G-Q, H-S
2. E-R, F-P, G-S, H-Q
3. E-R, F-P, G-Q, H-S
4. E-P, F-R, G-S, H-Q

+1

H-S is true coz strings generated by this grammar satisfies the definition of an even length palindrome string. this rules out B and D options.

G-Q is confirmed as both options A and C has it as true.

E-R is true coz R is the only grammar that checks: what$(w)$ has occurred earlier is present afterwards This equals the definition of E

Hence, option C is true.

edited by
+1
Sir, Can you explain why G - Q ??
+6
I have no clue there. Guess the reason given in answer is the best :)
0
What's wrong with F-R? Formal parameter declaration must be in exaclty same fashion as actual parameter called! F-R also makes absolute sense. Why (A) is not the answer?
+27
$X\: \rightarrow XbX \mid XcX \mid dXf \mid g$
Here,
$X$ is $expr$
$b$ and $c$ are operators
$d$ is opening paranthesis  "$\big($"
$f$ is closing paranthesis "$\big)$"
$g$ is a variable.

Now it says,
$expr\: \rightarrow expr \text{ operator1 } expr \mid expr \text{ operator2 } expr \mid \big(expr\big) \mid var$
+1

Why not is E matched with P?

as given in the previous question:- https://gateoverflow.in/2461/gate1994_1-18 CSL checks whether a variable has been declared before its use and I think P is CSL whereas R is DCFL?

So why not E with p?

Plz explain..

We can match H-S just by checking the grammar we can generate all the even lenght palindromes

So we left with option A and C(only in these options H-S matched)

In both the cases G-Q so we left with matching for E and F

For E the grammar should check the identifiers are declared before their use So R is more accurate since the grammar is

L={wcw ∣ w∈ (a∣b) } where w is occured earlier and then it is used which matches with checking declaratation of identifiers

and also E-P makes no sense

Therefore we can conclude C. E-R, F-P, G-Q, H-S

edited
–1 vote

0