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

Why: Type-3 (regular) → right-linear (IV); Type-2 (context-free) → $V \to (V\cup\Sigma)^*$ (I); Type-1 (context-sensitive) → context-preserving form (II); Type-0 (unrestricted) → any string to any string (III).

In a multi-tape Turing machine, suppose there are $k$ tapes.

At any step, the machine reads:

$k$ tape symbols

So, input to transition function is:

$current\ state = Q$

$k\ tape\ symbols = \Gamma^k$

Hence input side is:

$Q \times \Gamma^k$

After transition, the machine decides:

new state $Q$

new symbols to write on $k$ tapes, that is $\Gamma^k$

movement of $k$ tape heads, that is ${L,R,S}^k$

Hence output side is:

$Q \times \Gamma^k \times {L,R,S}^k$

Therefore,

$\delta: Q \times \Gamma^k \to Q \times \Gamma^k \times {L,R,S}^k$

In pumping lemma for regular languages, a string is divided as:

$w=xyz$

The conditions are:

$|xy| \le n$

$|y| > 0$

$xy^iz \in L$ for all $i \ge 0$

Here, $|y|>0$ means $y$ cannot be empty.

So, the minimum length of $y$ is:

$1$

In LR item notation, a dot is placed somewhere on the right side of a production.

But $\epsilon$ means empty string.

So, for the production:

$A \to \epsilon$

there is actually no symbol on the right side.

Therefore, the LR item is written as:

$A \to .$

This means the production is already complete.

Initial state is:

$q_0$

From $q_0$, using $\epsilon$ move:

$q_0 \xrightarrow{\epsilon} q_1$

From $q_1$, again using $\epsilon$ move:

$q_1 \xrightarrow{\epsilon} q_2$

So, without reading any input symbol, we can reach:

$q_2$

But final state is:

$q_3$

Now from $q_2$, on input symbol $a$:

$q_2 \xrightarrow{a} {q_2,q_3}$

So, after reading one $a$, we can reach final state $q_3$.

Therefore, the minimum string is:

$a$

Length of $a$ is:

$1$

Scaling matrix is:

$M=\left[\matrix{0.5\quad 0\cr 0\quad 1.5}\right]$

Here,

Horizontal scaling factor is:

$S_x=0.5=\frac{1}{2}$

So, horizontal value becomes half.

Therefore, statement $4$ is true.

Vertical scaling factor is:

$S_y=1.5=\frac{3}{2}$

So, vertical value increases by three halves.

Therefore, statement $2$ is true.

Correct statements are:

$2$ and $4$

The given regular expression is $aa^*bb^*cc^dd^$, where:

• $a^*$ denotes zero or more occurrences of $a$
• $b^*$ denotes zero or more occurrences of $b$
• $c^*$ denotes zero or more occurrences of $c$
• $d^*$ denotes zero or more occurrences of $d$

1. The language generated by the regular expression

$L={a^n b^n c^m d^m \mid n \ge 1, m \ge 1}\cup{a^n b^m c^m d^n \mid n \ge 1, m \ge 1}$

consists of strings where $a$'s are followed by $b$'s, which are followed by $c$'s, and then $d$'s.

Each of these letters $a, b, c, d$ can occur one or more times in any order. For example, $abcd$, $aabcdd$, etc. So the language $L$ can generate regular expressions $aa^*bb^*cc^dd^$.

2. The Context Free Language for the given expression is:

$S \to AB \mid C$

$A \to aAb \mid ab$

$B \to cBd \mid cd$

$C \to aCd \mid aDd$

$D \to bDc \mid bc$

This is true.

For example:

$S \to AB \mid C$

$S \to abcd$

3. The language generated by this expression is equal number of $a$'s, followed by equal number of $b$'s, followed by equal number of $c$'s and followed by equal number of $d$'s.

This statement is false.

The regular expression $aa^*bb^*cc^dd^$ generates strings where each letter $a, b, c, d$ can occur one or more times, but there is no constraint that the number of occurrences of each letter must be equal.

For example, the regular expression can generate strings like $abcd$, $abccdd$, $aaaabbbccddd$, etc., where the number of occurrences of each letter is not necessarily equal.

So option C is the correct answer.