Solution

Solution

Tokens are the smallest meaningful units of a program.

Break the statement:

for | i | in | range | ( | begin | : | end | : | step | ) | :

Tokens:

for

i

in

range

(

begin

:

end

:

step

)

:

Total tokens = 12

Solution

Solution

Solution

While simplifying a CFG, the safest order is:

First remove $\epsilon$-productions.

Then remove unit productions.

Finally remove useless symbols and productions.

Reason:

After removing $\epsilon$-productions, new unit productions may be created.

After removing unit productions, some symbols may become useless.

So, useless symbols should be removed at the end.

Correct order is:

$\epsilon$-productions → Unit productions → Useless symbols and productions

Solution

Solution

A grammar is ambiguous if a string generated by it has more than one parse tree.

Equivalent definitions:

• More than one leftmost derivation

• More than one rightmost derivation

Thus the correct statements are:

B and C.

Solution

$M1$ is used when the machine is in state $q1$ and reads symbol $c$.

In this stage, the machine has already marked one $a$ as $X1$ and is searching for the corresponding $c$.

So, when it finds $c$, it marks it as $X2$ and moves left to return back.

Therefore,

$M1=(q2,X2,L)$

Solution

$M2$ is in state $q0$ on symbol $X1$.

In standard Turing Machine design for this language, $X1$ represents an already marked $a$.

So, the machine should skip $X1$ and move right to search for the next unmarked $a$.

Correct move should be:

$(q0,X1,R)$

But this option is not present in the given options.

Solution

$M3$ is in state $q3$ on symbol $a$.

State $q3$ is used after matching all $a$'s with $c$'s. Now the machine works on $b$'s and $d$'s.

So, if the machine sees an unmarked $a$ in state $q3$, it means the string is not in the correct form.

Hence, it is an error entry.

Solution

$M4$ is in state $q5$ on symbol $Y1$.

Here, $Y1$ represents a marked $b$.

After marking one corresponding $d$ as $Y2$, the machine moves left and reaches $Y1$.

Now it should move right and again go to state $q3$ to search for the next unmarked $b$.

Therefore,

$M4=(q3,Y1,R)$

Solution

Solution

In LR parsing, shift-reduce conflicts occur when the parser can either shift the next input symbol or reduce using a rule.

These conflicts are resolved using operator precedence and associativity rules.

Solution

$M5$ is in state $q4$ on symbol $X2$.

Here, $X2$ represents an already marked $c$.

In state $q4$, the machine is moving right to find an unmarked $d$ corresponding to a marked $b$.

So, when it sees $X2$, it simply skips it and moves right.

Therefore,

$M5=(q4,X2,R)$

Solution

Solution

Solution

• LL(0) is the weakest (no lookahead, top-down).
• LR(0) is stronger than LL(0) (bottom-up, no lookahead).
• SLR(1) adds 1-symbol lookahead using FOLLOW sets → accepts more grammars than LR(0).
• LALR(1) merges LR(1) states; more powerful than SLR(1) but below LR(1).
• LR(1) is the most powerful among these deterministic bottom-up parsers.

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

This grammar produces the dangling-else problem.

In such cases the else can be associated with more than one if, producing more than one parse tree.

Thus the grammar is ambiguous.

Solution

Solution

Solution

Solution

$A\rightarrow aB|a$ → Regular grammar → Finite Automata → IV

$A\rightarrow BC|a$ → Chomsky Normal Form → III

$LL(1)$ grammar → Recursive Descent Parser → I

Halting problem → Turing Machine → II

Matching:

$A\rightarrow IV$

$B\rightarrow III$

$C\rightarrow I$

$D\rightarrow II$

Solution

Solution

Solution

Chomsky hierarchy order:

Regular Languages

< Context-Free Languages

< Context-Sensitive Languages

< Recursively Enumerable (Unrestricted) Languages

Thus order:

C → A → B → D

Solution

Chomsky hierarchy order:

Regular Languages

< Context-Free Languages

< Context-Sensitive Languages

< Recursively Enumerable (Unrestricted) Languages

Thus order:

C → A → B → D

Solution

Solution

Solution

Solution

A compiler stores information about variables, functions, identifiers and their attributes in a symbol table.

Attributes may include name, type, scope, address and value.

Therefore, the data structure used for managing variables and their attributes is symbol table.

Solution

Given expression is

$(ij)+(e+f)(a*b+c)$

Count each arithmetic operation:

$i*j$ gives $1$ operation.

$e+f$ gives $1$ operation.

$a*b$ gives $1$ operation.

$a*b+c$ gives $1$ operation.

$(e+f)(ab+c)$ gives $1$ operation.

Finally,

$(ij)+[(e+f)(a*b+c)]$ gives $1$ operation.

Total operations:

$1+1+1+1+1+1=6$

Solution

Solution

Constant folding is a compiler optimization technique.

In this technique, constant expressions are evaluated at compile time.

Here,

$4*2.14=8.56$

So, replacing $4*2.14$ by $8.56$ is constant folding.

Solution

Solution

A shift-reduce parser uses an input buffer to read the input string.

It uses a stack to store grammar symbols during parsing.

In table-driven shift-reduce parsing, a parse table is also used to decide shift and reduce actions.

Therefore, shift-reduce parser consists of input buffer, stack and parse table.

Solution

The regular expression is

$a^*b(a+b)$

It means:

Any number of $a$'s, followed by one $b$, followed by either $a$ or $b$.

So, strings accepted are like:

$ba,\ bb,\ aba,\ abb,\ aaba,\ aabb$

Minimum DFA states needed:

State $q_0$: Initial state, reads any number of $a$'s.
State $q_1$: After reading required $b$.
State $q_2$: Final state after reading last symbol $a$ or $b$.
State $q_d$: Dead state for extra or invalid symbols.

Thus, total minimum states are

$4$

Solution

Solution

For $(a)$:

$L_3$ is a recursive language.

Complement of a recursive language is also recursive.

So,

$\overline{L_3}$ is recursive.

Also, $L_4$ is recursively enumerable.

Union of a recursive language and a recursively enumerable language is recursively enumerable.

Therefore,

$\overline{L_3}\cup L_4$ is recursively enumerable.

So,

$(a)\rightarrow(ii)$

For $(b)$:

$L_2$ is context-free language.

Every context-free language is recursive.

So, complement of $L_2$ is also recursive.

Also, $L_3$ is recursive.

Union of two recursive languages is recursive.

Therefore,

$\overline{L_2}\cup L_3$ is recursive.

So,

$(b)\rightarrow(iii)$

For $(c)$:

$L_1$ is regular.

Regular languages are closed under Kleene star.

So,

$L_1^*$ is regular.

Intersection of a regular language and a context-free language is context-free.

Therefore,

$L_1^*\cap L_2$ is context-free.

So,

$(c)\rightarrow(i)$

Hence, correct matching is

$(a)-(ii);\ (b)-(iii);\ (c)-(i)$

Solution

Solution

To decide whether a context-free language is finite or infinite, we can convert the CFG into a non-redundant CFG in CNF.

Usually, the CNF grammar is considered for $L-{\Lambda}$.

After converting into CNF, we check whether there is any recursive derivation or cycle among variables.

If such a recursive structure exists, then the language is infinite.

If no such recursive structure exists, then the language is finite.

So, the correct construction is given in statement $(c)$.

Solution

Solution

Given grammar is

$S\to XY$

$X\to YaY\mid a$

$Y\to bbX$

Since $S\to XY$, the string contains one part from $X$ and one part from $Y$.

Now, $X$ can generate at least one $a$.

Also, $Y\to bbX$, so $Y$ also contains one $X$, which again gives at least one $a$.

Therefore, every string generated by $S$ has at least two $a$'s.

So, statement $(c)$ is true.

Also, every use of $Y$ contributes $bb$, that is $2$ occurrences of $b$.

So, the number of $b$'s is always in multiple of $2$.

Therefore, statement $(d)$ is true.

The grammar contains $bb$, so alternate $a$ and $b$ condition is false.

Also, consecutive three $a$'s are not necessarily produced.

Solution

Solution

Solution

Solution

Solution

Solution

In $G_2$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid \lambda$

In $G_4$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid SSS\mid \lambda$

The only extra production in $G_4$ is:

$S\rightarrow SSS$

But this production is already possible using $S\rightarrow SS$ again and again.

For example:

$S\rightarrow SS\rightarrow SSS$

So, $SSS$ does not generate anything extra.

Hence, $G_2$ and $G_4$ generate the same language.

Solution

Given language is:

$L={a^n b^{n-3}\mid n>2}$

When $n=3$:

$a^3b^0=aaa$

When $n=4$:

$a^4b^1=aaaab$

When $n=5$:

$a^5b^2=aaaaabb$

So, every string starts with at least three $a$ symbols.

After that, for every extra $a$, one $b$ is added at the end.

Grammar:

$S\rightarrow aaaA$

$A\rightarrow aAb\mid \lambda$

If $A\rightarrow \lambda$, then string is:

$aaa$

If $A\rightarrow aAb$, then it generates:

$aaaab,\ aaaaabb,\ldots$

So, this grammar generates $a^n b^{n-3}$ for $n>2$.

Solution

From production:

$S\rightarrow 0A$

and

$A\rightarrow 00A\mid \lambda$

So, $A$ can generate:

$\lambda,\ 00,\ 0000,\ldots$

Hence, $S$ generates:

$0,\ 000,\ 00000,\ldots$

This is represented by:

$(00)^*0$

Now consider:

$S\rightarrow 0BB$

But $B$ has productions:

$B\rightarrow 1B\mid 11C$

and

$C\rightarrow B$

Here, $B$ never terminates into $\lambda$ or any final terminal-only string.

So, this branch does not generate any valid finite string.

Hence, the grammar generates only:

$L((00)^*0)$

Solution

Solution

Solution

Given language:

$L={a^n b^n\mid n\ge 0}$

This is a context free language.

Now check each statement.

For $S_1$:

$L^2=L\cdot L$

Context free languages are closed under concatenation.

So, $L^2$ is also context free.

Hence, $S_1$ is true.

For $S_2$:

$L^k$ means concatenation of $L$ with itself $k$ times.

For any fixed $k\ge 1$, context free languages are closed under finite concatenation.

So, $L^k$ is context free.

Hence, $S_2$ is true.

For $S_3$:

$L^*$ is context free because context free languages are closed under Kleene star.

Also, for this specific language $L={a^n b^n\mid n\ge 0}$, its complement $\overline{L}$ is also context free.

So, $\overline{L}$ and $L^*$ both are context free languages.

Hence, $S_3$ is true.

Therefore, all three statements $S_1,\ S_2$ and $S_3$ are correct.

Solution

Solution

$L_1={a^n b^n c^m}\cup{a^n b^m c^m}$ is a standard example of an inherently ambiguous language.

Reason: strings of the form $a^n b^n c^n$ can be generated from both parts:

First part: $a^n b^n c^m$ when $m=n$

Second part: $a^n b^m c^m$ when $m=n$

So, ambiguity is unavoidable for $L_1$.

Now,

$L_2={ww^R\mid w\in{a,b}^*}$ is the language of even length palindromes.

This language is context-free and not inherently ambiguous.

Solution

In Chomsky Normal Form, every production must be of the form:

$A\rightarrow BC$

or

$A\rightarrow a$

If a production has maximum $K$ symbols on the right side, then to convert it into binary productions, at most $K-1$ productions are needed.

So, for $|P|$ productions, maximum productions required are:

$(K-1)|P|$

Also, for terminals, we may need separate productions for each terminal.

Number of terminals $=|T|$

So, total maximum number of productions:

$(K-1)|P|+|T|$

Solution

The Chomsky hierarchy and decidability relation is:

Context-free languages $\subseteq$ Context-sensitive languages

Context-sensitive languages $\subseteq$ Recursive languages

Recursive languages $\subseteq$ Recursively enumerable languages

So,

$L_1\subseteq L_2\subseteq L_4\subseteq L_3$

Solution

Checking whether two Turing machines accept the same language means checking:

$L(M_1)=L(M_2)$

This is undecidable.

So, $S_1$ is true.

For $S_2$:

Checking whether:

$L(M_1)\subseteq L(M_2)$

for arbitrary Turing machines is also undecidable.

So, $S_2$ is also true.

Solution

For pair $(A,B)$:

Take sequence of indices:

$3,4,1$

From $A$ side:

$A_3A_4A_1=11\ 101\ 001=11101001$

From $B$ side:

$B_3B_4B_1=111\ 010\ 01=11101001$

Both strings are equal.

So, pair $(A,B)$ has a PCP solution.

For pair $(C,D)$:

Starting must be with first pair because only it gives matching prefix:

$C_1=00,\ D_1=0$

After this, extra $0$ remains on upper side. Repeating first pair keeps increasing extra zeros, and other pairs do not match the required prefix properly.

So, pair $(C,D)$ has no PCP solution.

Solution

Solution

Solution

The language $L={a,b}^*$ means all possible strings over $a$ and $b$, including null string $\epsilon$.

So, an automaton recognizes $L={a,b}^*$ if every string made from $a$ and $b$ is accepted.

In A, $q_0$ is the initial and final state, and both $a$ and $b$ return to $q_0$.

So, A accepts all strings over ${a,b}$.

In B and C, $q_0$ and $q_1$ are final states, so all possible moves remain in final states.

So, B and C also accept all strings over ${a,b}$.

In D, $q_0$ is final and from $q_0$, both $a$ and $b$ return to $q_0$. Other states do not affect acceptance because starting from $q_0$, every input stays at $q_0$.

So, D also accepts all strings over ${a,b}$.

Therefore, A, B, C and D recognize $L={a,b}^*$.

Solution

Syntax Directed Translation is used in:

Type checking

Intermediate code generation like 3-address code

Construction of syntax tree

But valid tokens are recognized by lexical analyzer, not by syntax directed translation.

So, correct statements are A, B and C.

Correct option is:

$\boxed{(a)\ \text{A, B and C}}$

Solution

Given distance from router $R$ to its neighbors:

$R\to X=3$

$R\to Y=2$

$R\to Z=5$

For router $P$:

Via $X$: $3+7=10$

Via $Y$: $2+6=8$

Via $Z$: $5+5=10$

Minimum distance from $R$ to $P$ is $8$ via $Y$.

So, statement C is true.

For router $Q$:

Via $X$: $3+4=7$

Via $Y$: $2+6=8$

Via $Z$: $5+8=13$

Minimum distance from $R$ to $Q$ is $7$ via $X$.

So, statement B is true.

Correct statements are B and C only.

Correct option is:

$\boxed{(a)\ \text{B and C only}}$

Solution

Syntax trees (Abstract Syntax Tree – AST) are used in later compiler phases.

(A) Type Checking → Done using syntax tree ✔

(B) Code Generation → Uses syntax tree ✔

(C) Code Optimization → Uses syntax tree representation ✔

(D) Error Handling → Mainly done during lexical / syntax analysis ✘

Thus correct tasks:

(A), (B), (C)

Solution

For LL parsing:

Initial configuration: $$S w$$

Final configuration: $$$$

For LR parsing:

Initial configuration: $$w$$

Final configuration: $$S$$

So,

A → III
B → II
C → I
D → IV

Correct option is:

$\boxed{(b)\ A-III,\ B-II,\ C-I,\ D-IV}$

Solution

Standard compiler phases:

Lexical Analysis

Syntax Analysis

Semantic Analysis

Intermediate Code Generation

Code Optimization

Thus order:

(A) → (C) → (B) → (D) → (E)

Solution

Solution

In regular expressions, operator precedence from highest to lowest is:

$Star > Concatenation > Union$

Therefore, from lowest to highest:

$Union < Concatenation < Star$

Correct option is:

$\boxed{(c)\ \text{Union, Concatenation, Star}}$

Solution

(A) True

Regular grammar productions follow

$A \rightarrow aB$ or $A \rightarrow a$

(B) False

Regular grammar less powerful than CFG

(C) True

Regular grammar ↔ Finite automata equivalence

(D) False

Regular languages are recognized by finite automata

Solution

Solution

Solution

Every regular language can be accepted by a finite automaton, and every finite automaton can be simulated by a Turing Machine.

So, statement A is true.

Every context free language can be accepted by a pushdown automaton, and every pushdown automaton can also be simulated by a Turing Machine.

So, statement B is also true.

Correct option is:

$\boxed{(d)\ \text{Statement A and Statement B both are true}}$

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

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

Solution

Solution

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$

Solution

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$

Solution

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.

Solution

Solution

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$

Solution

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$

Solution

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.

Solution

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$

Solution

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

Solution

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

Solution

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.

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution