The Gateway to Computer Science Excellence

+41 votes

Match the following:

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

- $\text{E-P, F-R, G-Q, H-S}$
- $\text{E-R, F-P, G-S, H-Q}$
- $\text{E-R, F-P, G-Q, H-S}$
- $\text{E-P, F-R, G-S, H-Q}$

0

If anyone is interested, the languages for checking that identifiers are declared before use and matching formal params to actual params of functions are both described in the dragon book on compilers.

The existence of these constructs raises the level of programming languages like C/C++ from context free to context sensitive (both are CSLs).

The existence of these constructs raises the level of programming languages like C/C++ from context free to context sensitive (both are CSLs).

+41 votes

Best answer

H-S is true because 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 because 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.

+1

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?

+68

$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$

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$

+2

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..

+4

here F-R is not valid always because formal parameter name may differ with actual parameter and R is L={wcw/..} which means corresponding parameters name should be same .

calling function can be like fun(int p,int q,int r) and called function can be like fun(int x,int y,int z).

So in this case string will be something like pqrcxyz which doesn,t belong to L.

calling function can be like fun(int p,int q,int r) and called function can be like fun(int x,int y,int z).

So in this case string will be something like pqrcxyz which doesn,t belong to L.

+5

Abhishek Rai 2 I think the datatype of the formal arguments are matched with that of the actual arguments. What you are doing appears like you are trying to match the variable names which is not required. Here in your calling functions no. of 'int' type parameters is 3 and the same is for the case of called function where no. of 'int' type parameters is also 3. So it is like {a^{3}b^{0}c^{3}d^{0}} where (a and c) stand for no. of int type arguments and (b and d) for some other data type like char.

Example:

calling function --> Fun(int m,int n, char o) // a^{2}b^{1}

called function --> Fun(int x,int y, char s) // c^{2}d^{1}

In that way the matching is done. Feel free to correct me if you find it wrong.

+7 votes

**The Answer is C**

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**

+2 votes

The grammar in S {X $\rightarrow$ bXb | cXc | ϵ} derives all even length Palindromes, So H matches with S.

F matches with P, Number of formal parameters in the declaration…. matches with {L={ $a ^{n}$ $b ^{m} c ^{n} d ^{m}$ | m,n >=1}

Since, $a ^{n}$ $b ^{m}$ corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and $ c ^{n} d ^{m}$ corresponds to actual parameter used in function.

Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.

F matches with P, Number of formal parameters in the declaration…. matches with {L={ $a ^{n}$ $b ^{m} c ^{n} d ^{m}$ | m,n >=1}

Since, $a ^{n}$ $b ^{m}$ corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and $ c ^{n} d ^{m}$ corresponds to actual parameter used in function.

Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.

52,345 questions

60,469 answers

201,795 comments

95,272 users