The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
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

 

asked in Theory of Computation by Veteran (59.4k points) | 2.2k views
+1

4 Answers

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

answered by Boss (30.6k points)
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..

+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

answered by Boss (11.3k points)
edited by
–1 vote

Answer is C.

answered by Active (4.2k points)
0
please explain the answer..
–2 votes

Dear reviewers Pls see page 146 in the book Compilers: Principles, techniques and tools by AHO, SHETI AND ULLMAN Book (1st Edition) for explanation on (P) and (R)

answered by (43 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,780 questions
41,758 answers
118,934 comments
41,400 users