The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 votes

Match the following:


Checking that identifiers are declared before their use


$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$


Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function


$X\: \rightarrow XbX \mid XcX \mid dXf  \mid g$


Arithmetic expressions with matched pairs of parentheses


$L\: = \left\{wcw\mid w \: \in \left(a\mid b\right)^* \right\}$




$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 (68.8k points) | 1.9k views

4 Answers

+29 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 Veteran (30.5k points)
selected by
Sir, Can you explain why G - Q ??
I have no clue there. Guess the reason given in answer is the best :)
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?
$X\: \rightarrow XbX \mid XcX \mid dXf \mid g$
$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$

Why not is E matched with P?

as given in the previous question:- 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 Veteran (13.2k points)
edited by
–1 vote

Answer is C.

answered by Loyal (4.1k points)
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 (33 points)

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

32,443 questions
39,188 answers
36,563 users