The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 votes

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

- E-P, F-R, G-Q, H-S
- E-R, F-P, G-S, H-Q
- E-R, F-P, G-Q, H-S
- E-P, F-R, G-S, H-Q

+30 votes

Best answer

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.

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$

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 408
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,780 questions

41,758 answers

118,934 comments

41,400 users