UGC NET Computer Science Compiler Design Previous Year Questions (PYQs) – Page 1 of 12
Study Stuff for MCA Examinations
Solution
The number of tokens in the following line:
for i in range(begin : end : step) :
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
What is the safest order while simplifying Context Free Grammar?
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
$F(A,B,C,D)=\sum(0,1,2,3,6,12,13,14,15)$
is/are
(A) $A'B' + AB + A'C'D'$
(B) $A'B' + AB + A'CD'$
(C) $A'B' + AB + BC'D'$
(D) $A'B' + AB + BCD'$
Choose the correct answer from the options given below:
Solution
$0,1,2,3,6,12,13,14,15$
$A'B'$ covers minterms $0,1,2,3$
$AB$ covers minterms $12,13,14,15$
Remaining minterm is $6$
Option (B):
$A'CD'$ covers minterms $2,6$
Both are present in the function.
So, option (B) is correct.
Option (D):
$BCD'$ covers minterms $6,14$
Both are present in the function.
So, option (D) is also correct.
Options (A) and (C) include minterm $4$, which is not present in the function.
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.
A Turing Machine for the language
$L=a^n b^m c^n d^m \mid n \ge 1,\ m \ge 1$ is designed.
The resultant model is
$M=({q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_f},{a,b,c,d},{a,b,c,d,X_1,X_2,Y_1,Y_2},\delta,q_0,B,{q_f})$
and part of $\delta$ is given in the transition table.
You need to write the following questions based on design of Turing Machine for the given language.
Note that, while designing the Turing Machine $X_1$ and $X_2$ are used to work with $a$'s and $c$'s and $Y_1$ and $Y_2$ are used to handle $b$'s and $d$'s of the given string.
What is the Move in the cell with number 'M1' of the resultant Table ?
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)$
A Turing Machine for the language
$L=a^n b^m c^n d^m \mid n \ge 1,\ m \ge 1$ is designed.
The resultant model is
$M=({q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_f},{a,b,c,d},{a,b,c,d,X_1,X_2,Y_1,Y_2},\delta,q_0,B,{q_f})$
and part of $\delta$ is given in the transition table.
You need to write the following questions based on design of Turing Machine for the given language.
Note that, while designing the Turing Machine $X_1$ and $X_2$ are used to work with $a$'s and $c$'s and $Y_1$ and $Y_2$ are used to handle $b$'s and $d$'s of the given string.
What is the Move in the cell with the number $M2$ of the resultant Table?
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.
A Turing Machine for the language
$L=a^n b^m c^n d^m \mid n \ge 1,\ m \ge 1$ is designed.
The resultant model is
$M=({q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_f},{a,b,c,d},{a,b,c,d,X_1,X_2,Y_1,Y_2},\delta,q_0,B,{q_f})$
and part of $\delta$ is given in the transition table.
You need to write the following questions based on design of Turing Machine for the given language.
Note that, while designing the Turing Machine $X_1$ and $X_2$ are used to work with $a$'s and $c$'s and $Y_1$ and $Y_2$ are used to handle $b$'s and $d$'s of the given string.
What is the Move in the cell with number $M3$ of the resultant Table?
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.
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
