Compiler Design & TOC Test - 1 - PDF Flipbook

319 Views
49 Downloads
PDF 6,427,752 Bytes

Download as PDF

REPORT DMCA

---

GATE
CSE

CompilerDesign
+

TheoryofComputation

Test-01Solutions

COMPILER DESIGN + THEORY OF COMPUTATION
1. Context free languages are closed under:

a) Union, intersection
b) Union, Kleene closure
c) Intersection, complement
d) Complement, Kleene Closure
Answer: (b)
Solution:
Since CFLs are closed w.r.t union and Kleene closure.
CFLs are not closed w.r.t intersection and complement.
L1 = {an bn ci | i, n ≥ 1} & L2 = {aj bm cm | j, m ≥ 1} are CFLs.
Their intersection is L1 ∩ L2 = {ak bk ck | K ≥ 1} which is not a
CFL but a CSL. So CFLs are not closed under intersection. As
CFLs are closed under union by De-Morgan's law they cannot
be closed under complement.
2.The language accepted by this automaton is given by the regular
expression
a) a*ab* ab* ab*
b) (a + b)*
c) b*a(a + b)*
d) b*ab* ab*
Answer: (c)
Solution:
As the start state is not a final state ' ' is not accepted by the F.A
so (b) cannot be the answer.

1

As aaa is accepted by the F.A we can ruled out choice (d) as it
does not contain aaa. The string a must be accepted by the F.A
this ruled out (a) as (a) needs at least three a's.
By elimination the answer is (c). We can justify this by
minimizing the DFA. State q3 can be deleted as there is no
every of contain q3.

Create the partitions for the minimization Algorithm.
{[q0, q2]*, [q1]}
We cannot refine for that so q0&q2 can be merged. The minimal
DFA is

This exactly accepts b*a(a + b)*. So the answer is (c).
3. A computing architecture, which allows the user to use

computers from multiple administrative domains to reach a
common goal is called as
a) Grid Computing
b) Neutral Networks

2

c) Parallel Processing
d) Cluster Computing
Answer: (a)
Solution:
Grid computing is the collection of computer resources from
multiple locations to reach a common goal.
4. Which of the following are regular sets?
I.An b2m | n ≥ 0, m ≥ 0}
II.{an bm |n = 2m}
III.{an bm |n ≠ m}
IV.{xcy |x, y {a, b}*}
a) I & IV only
b) I and III only
c) I only
d) IV only
Answer: (a)
Solution:
Case (I): L = an (b2)m & hence is regular.
Case (IV): {(x, y)| x, y ∈ (a + b)*}

= (a + b)* c (a + b)*& hence is regular.
By elimination the answer must be (a).

3

5. Which of the following statements are true?
1. Every left-recursive grammar can be converted to a right-
recursive grammar and vice-versa.
2. All e-productions can be removed from any context-free
grammar by suitable transformations
3. The language generated by a context free grammar all of
whose productions are of the form X→ w or X→ wY (where,
w is a string of terminals and y is a non-terminal), is always
regular
4. The derivation trees of strings generated by a context-free
grammar in Chomsky Normal form are always binary trees
a) l, 2, 3 and 4
b) 2, 3 and 4 only
c) l, 3 and 4 only
d) l, 2 and 4 only
Answer: (c)
Solution:
Case (i):
Using the GNF we can convert left recursive rules to right
recursive rules. By considering the reversal of a CFG and GNF
we can convert a right recursive rule to a left recursive one.
Case (ii):
All - productions can be removed from a CFG. However of
the language generated contains ' ' then there must be a rule
S→ , where S is the starting symbol. So, (ii) is false.

4

Case (iii):
If the rules of a CFG are X→ w/w Y then the grammar is a
right linear grammar & hence generates a regular set.
Case (iv):
CNF has rules of the form A→BC/a. A→BC yields two
children B & C to the root A. A → a yields are child node a to
the root A. Hence the derivation tree is always a binary tree.
6. Which of the following is true?
a) The complement of a recursive language is recursive.
b) The complement of a recursively enumerable language is

recursively enumerable.
c) The complement of a recursive language is either recursive

or recursively enumerable.
d) The complement of a context-free language is context-free.
Answer: (a)
Solution:
Case (a):
Recursive sets are accepted by halting TMs. Just interchange
the accepting & rejecting conditions when the machine halts.
So this is true.
Case (b):
The R.E sets are not closed under complement. The
complement of a R.E set may not be R.E.

5

Case (c):
The R.E sets complements that are not closed under are R.E or
recursive in general the complement of a R.E set is not R.E.
7. Let A and B be finite alphabets and let # be a symbol outside
both A and B. Let f be a total function from A* to B*. We say f
is computable if there exists a Turing machine M which given
an input x in A*, always halts with f(x) on its tape. Let Lf denote
the language {x # f(x) | X ∈ A*}. Which of the following
statements is true?
a) f is computable if and only if Ls is recursive
b) f is computable if and only if L1 is recursively enumerable
c) If f is computable then L1 is recursive, but not conversely
d) If f is computable then Ls is recursively enumerable, but not

conversely
Answer: (a)
Solution:
As we know that A Language L is said to be recursive if a TM
halts on all strings of L and L1.
Here also Turing Machine halts on given input x in A with f(x)
on its tape.

6

8. Let X be a recursive language and Y be a recursively
enumerable but not recursive language. Let W and Z be two
languages such that Y reduces to W, and Z reduces to X
(reduction means the standard many-one reduction). Which one
of the following statements is TRUE?
a) W can be recursively enumerable and Z is recursive.
b) W can be recursive and Z is recursively enumerable.
c) W is not recursively enumerable and Z is recursive.
d) W is not recursively enumerable and Z is not recursive.
Answer: (c)
Solution:
X → recursive
Y → REL but not recursive
� → W � -REC
Z→ �
Z is REC
W is recursive but not Recursively enumerable.

9. Consider the following languages
L1 = {0p1q0r | p, q, r ≥ 0}
L2 = {0p1q0r| p, q, r ≥ 0, p ≠ r}

Which one of the following statements is FALSE?
a) L2 is context-free
b) L1 ∩ L2 is context-free
c) Complement of L2 is recursive
d) Complement of L1 is context-free but not regular.

7

Answer: (d)
Solution:
L1 = Regular Language
L2 is Non regular and context free language
Intersection of CFL with regular is a CFL.
So L1 ∩ L2 is CFL
L2 is DCFL and DCFLs are closed under complement. So 12 is
DCFL
⇒ 12 is DCFL & CFL & CSL a regular Set
⇒ 12, is Recursive set
L1 is a Regular set.
So 11 is also regular and hence context free.
So, option (d) is FALSE.
L1 = 0*1*0* is regular.
By the pumping lemma for regular sets the inequality p ≠ r
makes L2 rot regular.
However it is a CFL as a PDA can be constructed which stacks
the initial 0's ignore the 1's & un-stacks the trailing. It can which
if p ≠ r. So L2 is a CFL. So (a) is ruled out. The intersection of a
CFL & a regular set is a CFL. So (b) is ruled out. As L2 is a
CFL, it is recursive. The Recursive sets are closed under
complement. So (c) is true.
Choice (d) can be shown to be fails.
L1 ∩ 0*1*0* = {0m1k0m / m, k ≥ 0}.
This is a standard CFL that is not regular.

8

10. Correspond to

p) .

q)

r)

s)
1. + 0(01*1 + 00)*01*
2. + 0(10*1 + 00)*0
3. + 0(10*1 + 10)*1
4. + 0(10*1 + 10)*10*

9

a) P – 2, Q – 1, R – 3, S – 4
b) P – 1, Q – 3, R – 2, S – 4
c) P – 1, Q – 2, R – 3, S – 4
d) P – 3, Q – 2, R – 1, S – 4
Answer: (c)
Solution:
By examination P accepts 00. This ruled out choice (d).
By examination P accepts 001. This ruled out choice (a).
By examination Q accepts 00. This ruled out choice (b)
By examination the answer is (c).
11. Match the following List – I with List – II
List - I
a) Checking that identifiers are declared before their use
b) Number of formal parameters in the declaration of a

function agrees with the number of actual parameters in a
use of that function
c) Arithmetic expressions with matched pairs of parentheses
d) Palindromes
List - II
p) L = {an bm cn | n ≥ 1, m ≥ 1}
q) X → X b X | X c X | d X f | g
r) L = {w c w | w (a|b)*}
s) X → b X b | c X c |

10

Codes:
a) E – P, F – R, G – Q, H – S
b) E – R, F – P, G – S, H – Q
c) E – R, F – P, G – Q, H – S
d) E – P, F – R, G – S, H – Q
Answer: (c)
Solution:
P: L = {an bm cn | n ≥ 1, m ≥ 1} to check the actual and formal
parameters
Q: X → X b X | X c X | d X f |g generates the arithmetic
expressions with matched pairs of parentheses.
R: L = {w c w | w (a|b)*} to check the declaration of variable
before usage.
S: X → b X b | c X c | to generate palindromes.
12. Let L1 = {w {0, 1}*| w has at least as many occurrences of
(110)'s as (011)'s}.
LetL2 = {w {0, 1}*| w has at least as many occurrences of
(000)'s as (111)'s}. Which one of the following is TRUE?
a) L1 is regular but not L2
b) L2 is regular but not L1
c) Both L1 and L2 are regular
d) Neither L1 nor L2 are regular
Answer: (d)
Solution:
Consider L = {ai bj | i ≤ j}. This is a CFL.

11

Which is not regular consider h(a) = 110, h(b) = 011.
h(L) ∩ (110)* (011)*(110)n (011)m, n ≤ m Which cannot be
regular
Alternatively L1I = L1 ∩ (110)*(011)* = {(110)I (011)j| i ≤ j}
Let h3(a) = 000,
h3(a) = 111,
ℎ3−1( 12) ∩ a*b* = L
Which is not regular so nether L1 and L2 is regular
13. Consider two decision problems Q1, Q2 such that Q1 reduces in
polynomial time to 3-SAT and 3-SAT reduces in polynomial
time to Q2.
Then which one of the following is consistent with the above
statement?
a) Q1 is in NP, Q2 is NP hard.
b) Q2 is in NP, Q1 is NP hard.
c) Both Q1 and Q2 in NP.
d) Both Q1 and Q2 are NP hard.
Answer: (a)
Solution:

So if 3-SAT is solved, Q1 can be solved.
3-SAT is in NP so Q1 is in NP.

12

Q2 is NP-hard but cannot be guaranteed to be NP.
So Q1 is in NP, Q2 is NP-hard.
14. Recursive languages are:
a) A proper superset of context free languages.
b) Always recognizable by pushdown automata.
c) Also called Type (0) languages.
d) Recognizable by Turing machines.
Answer: (c)
Solution:
The recursive languages are a superset of the CSLs, CFLs and
regular set. They properly include them. The recursive
languages are accepted by halting TMs and hence by the class of
TMs. They are a super set of the languages accepted by PDA.
The type (0) languages are the R.E sets which are a superset of
the recursive sets.
15. Which of the following statements are true?
1. Every left-recursive grammar can be converted to a right-
recursive grammar and vice-versa.
2. All e-productions can be removed from any context-free
grammar by suitable transformations

13

3. The language generated by a context free grammar all of
whose productions are of the form X→ w or X→ wY (where,
w is a string of terminals and y is a non-terminal), is always
regular

4. The derivation trees of strings generated by a context-free
grammar in Chomsky Normal form are always binary trees

a) l, 2, 3 and 4
b) 2, 3 and 4 only
c) l, 3 and 4 only
d) l, 2 and 4 only
Answer: (c)
Solution:
Case (i):
Using the GNF we can convert left recursive rules to right
recursive rules. By considering the reversal of a CFG and GNF
we can convert a right recursive rule to a left recursive one.
Case (ii):
All - productions can be removed from a CFG. However of the
language generated contains ' ' then there must be a rule S→ ,
where S is the starting symbol. So, (ii) is false.
Case (iii):
If the rules of a CFG are X→ w/w Y then the grammar is a right
linear grammar & hence generates a regular set.

14

Case (iv):
CNF has rules of the form A→BC/a. A→BC yields two
children B & C to the root A. A → a yields are child node a to
the root A. Hence the derivation tree is always a binary tree.
16. Consider the NPDA (Q = {q0, q1, q2} Σ = {0, l}, Γ = {0, 1, ⊥}, ,
q0, ⊥, F = {q2}), where (as per usual convention) Q is the set of
states, Σ is the input alphabet, Γ is the stack alphabet, is the
state transition function, q0 is the initial state, ⊥ is the initial
stack symbol, and F is the set of accepting states. The state
transition is as follows:

Which one of the following sequences must follow the string
101100 so that the overall string is accepted by the automaton?
a) 10110
b) 10010
c) 01010
d) 01001
Answer: (b)
Solution:
State q0: Input 0 or 1 is just pushed into the stack and no change
in state (or) a transition to state q1 take place in with no stack
alternates and input ignored.

15

State q1: A 0 on top of stack returns a 1 in the input & a 1 on
top of stack return a 0.
So (w center wc).
If only ⊥ is on stack go to final state.
State q0 is a push stack.
State q1 is a pop stack. (Push) = (Pop)
So transition first q1 to q1 is of the middle symbol.

a)

b)

c)

16

d)
Answer: (b)
17. The C language is
a) A context free language
b) A context sensitive language
c) A regular language
d) Parsable fully only by a Turing machine
Answer: (b)
Solution:
Case (a):
Check whether the number of parameters in the specification
and use of a function in C cannot be true by a CFL. Check
whether every variable is defined before it used cannot be done
by CFL.
Case (b):
The CSLs are sufficiently powerful to specify C. This is true.
Case(c):
Parenthesis matching cannot be done by a regular language. So
the C language cannot be regular.

17

Case (d):
Parsing techniques show that a C program can be parsed by a
PDA. So this statement is false.
18. Which of the statements related to compilers is wrong?
a) Lexical analysis is breaking the input into tokens
b) Syntax analysis is for parsing the phrase 40.
c) Syntax analysis is for analyzing the semantic
d) None of these
Answer: (c)
Solution:
Lexical analysis is breaking the input into tokens.
Syntax analysis is for parsing the phrase
Semantic analysis is for analyzing the semantic.
19. The language L= {an nn am bm| n ≥ 0, m ≥ 0} is
a) Context free but not linear
b) Context free and linear
c) Not Context free and not linear
d) Not Context free but linear
Answer: (a)
Solution:
Given language is L = {an bn am bm| n ≥ 0, m ≥ 0}
Grammar for L is
S → AB
A→ a A b|∈
A→ a B b|∈

18

Therefore, grammar is context-free but not leaner since
comparison is done here.
20. Match the following:
List-I
A. Context sensitive language
B. Regular grammar
C. Context free grammar
D. Unrestricted grammar
List-II
1. Deterministic finite automation
2. Recursive numerable
3. Recursive language
4. Pushdown automation
Codes:

A B CD
a) 2 1 4 3
b) 3 4 1 2
c) 3 1 4 2
d) 2 4 1 3
Answer: (c)
Solution:
Regular grammar- Deterministic finite-automation
Context-free grammar-pushdown automation
Context sensitive language –Recursive language
Unrestricted grammar-Recursive enumerable

19

21. The following Context-Free Grammar (CFG):
S→ a B| b A
A→ a| a S| b A A
B→ b| bS | a B B
Will generate
a) odd numbers of a’s and odd numbers of b’s
b) even numbers of a’s and even numbers of b’s
c) equal numbers of a’s and b's
d) different numbers of a’s and b’s
Answer: (c)
Solution:
Given CFG G is
S → aB| bA
A → a| aS| bAA
B → b| bS | aBB
Language of given grammar is
L(G) ={W # a’s =# b’s}
L(G) contains set of all strings with same number of a’s and b’s
over ∑(a, b).

22. Consider the following left associative operators in decreasing
order of precedence:
– Subtraction (highest precedence)
* Multiplication
$ Exponentiation (lowest precedence)
What is the result of the following expression?

20

a) – 61
b) 64
c) 512
d) 4096
Answer: (d)
Solution:
According to given condition = 3 – 2*4 $ 1 * 2 * * 3
= {{{3 – 2) * 4) $ ((1 * 2) * * 3)) = (4) $ (6) = 46 = 212 = 4096
23. Which of the regular expressions corresponds to this grammar?

S→ AB|AS, A → A| aA, B → b
a) aa*b+
b) aa*b
c) (ab)*
d) a(ab)*
Answer: (b)
Solution:
Given grammar is
S → AS|AB
A → a| aA
B→b
Language of above grammar is number of a’s at least one and
followed by exactly one b. (i.e., aa*b).

21

24. Consider the following two languages
L1:{0i 1j|gcd (i, j)=1}
L2 is any subset of 0*
Which of the following is correct?

a) L1 is reguler and L2* is not regular
b) L1 is not regular and L2* is reguler
c) Both L1 and L2* are reguler languages
d) Both L1 and L2* are not reguler languages
Answer:(b)
Solution:
L1 = {0i 1j|GCD ((I, j) = 1)} is context sensitive language but
neither context free nor reguler language.
L2 is any subset of 0* is reguler, because of unary alphabet.
Since(reguler)* is always reguler.
25. Consider a language A defined over the alphabet Σ = {0, 1} as
A = {0└n/2┘1n: n > = 0} the expression ⌊ /2⌋means the floor of
n/2, or what you get by rounding n/2 down to the nearest
integer. Which of the following is not an example of a string in
A?
a) 011
b) 0111
c) 0011
d) 001111
Answer: (c)

22

Solution:
Given language is:
A = {0⌊ /2⌋1n|n ≥ 0}
When, n = 0, string = ∈
N = 1, string =1
n = 2, string = 011
n = 3, string = 0111
n = 4, string = 01111
26. Tasks done in parsing are:
a) Check the validity of a source string
b) Determine the syntactic structure of a source string
c) Both (a)and (b)
d) None of these
Answer: (c)
Solution:
Parsing or synthetic analysis is the process of analyzing a string
of symbol, either in natural or computer languages, conforming
to the rules of a formal grammar.
27. The transition function for the language L= {w| (w) and
(w) are both odd} is given by
δ (q0, a) = q1δ (q0, b) = q2
δ (q1, a) = q0; δ (q1, b) = q3
δ (q2, a) = q3; δ (q2, b) = q0
δ (q3, a) = q2; δ (q3, b) = q1
The initial and final states of the automata are:

23

a) q0 and q0 respectively
b) q0 and q1 respectively
c) q0 and q2 respectively
d) q0 and q3 respectively
Answer: (d)
Solution:
Required DFA is combination of two DFA that one number of
a’s is odd and number of b’s are odd:

Final state Discription

q0 a's even, b’s even
q1 a's odd, b’s even
q2 a's even, b’s odd
q3 a's odd, b’s odd
Where q0 as initial (start) state
28. What is the output or the followings program? (Assume that the

appropriate pre-processor directives are included and there is no

syntax error)

main ()

{

char s [ ] = “ABCDEF”;

printf ("%C", * (& S [3]));

24

printf ("%s", S + 4);
printf ("%u", s);
/* Base address of S is 1000*/
}
a) ABCDEFGH1000
b) CDEFGH1000
c) DDEFGHH1000
d) DEFGH1000
Answer: (d)
Solution:

S is pointer of character array:

S[3] is character at index 3 of array S which is ’D’ and &(S[3])
is address of ‘D” but “%c” printed character at address of ‘D’
which is ‘D’ itself.
(S+4) escapes 4 character of array of S then remaining printed
till null which string is “EFGH”. “%u” printed address of array
S which is given as 1000.Therefore final printed is
“DEFGH1000”.

25

29. Consider a proposition given as:
"x ≥ 6, if x2 ≥ 25 and its proof as:
if x ≥ 6 then x2 =x. x ≥ 6.6 = 36 ≥ 25
Which of the following is correct with respected to the given
proposition and its proof?
S1: The proof shows the converse of what is to be provide
S2: the proof starts by assuming what are to be shows
S3: The proof is correct and there is nothing wrong
a) S1 only
b) S3 only
c) S1 and S2
d) S2 only
Answer: (c)
Solution:
Given x ≥ 6, if x2 ≥ 25
This is same as if x2 ≥ 25 then x ≥ 6
Proof: if x ≥ 6 then x2 = x. x ≥ 6.6 = 36 ≥ 25 is converse of what
he is saying. In proof they assume x ≥ 6 then x2 ≥ 35 will
proving correct.

30. if all the production rules have single non-terminal symbol on
the left side, the grammar defined is:
a) context free grammar
b) context sensitive grammar
c) unrestricted grammar
d) phrase grammar

26

Answer: (a)
Solution:
Context free grammar are those grammars in which the left hand
side of each production rule consists only a single non-terminal
symbol i.e., V→ (V + T)+

27