UGC NET Computer Science Compiler Design Previous Year Questions (PYQs) – Page 11 of 12

In compiler design, leaders are used to form basic blocks.

Rules for finding leaders:

1. The first instruction of the intermediate code is always a leader.

So, statement $1$ is true.

2. The middle instruction is not necessarily a leader.

So, statement $2$ is false.

3. Any instruction which is the target of a conditional or unconditional jump is a leader.

So, statement $3$ is true.

4. Any instruction immediately following a conditional or unconditional jump is also a leader.

So, statement $4$ is true.

Correct statements are:

$1,3,4$

Statement a:

Union with empty language gives the same language.

$\varphi + L = L$

So, statement a is true.

Statement b:

Concatenation with empty string does not change the language.

$\epsilon L = L\epsilon = L$

So, statement b is true.

Statement c:

Concatenation with empty language gives empty language.

$\varphi L = L\varphi = \varphi$

So, statement c is true.

Statement d:

This says concatenation with empty language gives $L$, which is false.

So, statement d is false.

Correct statements are:

a, b and c only

For $S \to aSa \mid aa$:

It generates strings:

$aa, aaaa, aaaaaa, \ldots$

So, length pattern is:

$2n$

Therefore,

a → II

For $S \to aaSaa \mid aa$:

It generates strings by adding two $a$'s on both sides.

So, it matches the given form IV.

Therefore,

b → IV

For $S \to aaaSaaa \mid aa$:

It generates lengths:

$2,8,14,20,\ldots$

This is:

$6n-4$

or

$((2n*3)-4)$

Therefore,

c → I

For $S \to aaaaSaaaa \mid aa$:

It generates lengths:

$2,10,18,26,\ldots$

This is:

$8n-6$

or

$((4*2n)-6)$

Therefore,

d → III

Correct matching:

a-II, b-IV, c-I, d-III

Compiler phases:

Lexical analysis → Tokenization

Syntax analysis → Parsing

Semantic analysis → Type checking, type conversion, scope checking

Optimization → Loop optimization, data flow analysis

Thus type conversion belongs to semantic analysis.