Theory of Computation
Multiple Choice Questions and Answers:-
1. The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S ? aSa
S ? aAa
A ? bB
B ? bB
B ? c is
a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1
Ans: B
2.The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S ? aAB
AB ? CD
CD ? CE
C ? aC
C ? b
bE ? bc is
a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1
Ans: C
3. The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S ? aS
A ? bB
B ? cC
C ? a is
a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1
Ans: A
4. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = (a, b, c}
P : S ? ABCD
BCD ? DE
D ? aD
D ? a
E ? bE
E ? c is
a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1
Ans: D
5. Consider the following CFG
S ? aB S ? bA
B ? b A ? a
B ? bS A ? aS
B ? aBB A ? bAA
Consider the following derivation
S ? aB
? aaBB
? aaBb
? aabSb
? aabbAb
? aabbab
This derivation is
a. a leftmost derivation
b. a rightmost derivation
c. both leftmost and rightmost derivation
d. neither leftmost nor rightmost derivation
Ans: D
6.Consider the following language
L = {anbncndn|n = 1}
L is
a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1
Ans: B
7.Consider the following language
L = {anbn|n = 1}
L is
a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1
Ans: A
8.Consider the following language
L = {anbmcpdq|n, m, p, q = 1}
L is
a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1
Ans: C
9.The following CFG is in
S ? AB
B ? CD
B ? AD
B ? b
D ? AD
D ? d
A ? a
C ? a
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form
Ans: C
10.The following CFG is in
S ? aBB
B ? bAA
A ? a
B ? b
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form
Ans: D
11.Which of the following CF language is inherently ambiguous?
a. {anbncmdm|n, m = 1}
b. {anbmcpdq|n = p or m = q, n, m, p, q = 1}
c. {anbmcpdq|n ? m ? p ? q}
d. {anbmcpdq|n ? m ? p ? q}
Ans: B
14.Can a DFSA simulate a NFSA
a. No
b. Yes
c. sometimes
d. depends on NFA
Ans: B
16.The concept of FSA is much used in this part of the compiler
a. lexical analysis
b. parser
c. code generation
d. code optimization
Ans: A
17.The concept of grammar is much used in this part of the compiler
a. lexical analysis
b. parser
c. code generation
d. code optimization
Ans: B
18.(a + b)(cd)*(a + b) denotes the following set
a. {a(cd)nb|n = 1}
b. {a(cd)na|n = 1} ? {b(cd)nb/n = 1}
c. {a(cd)na|n = 0} ? {a(cd)nb/n = 0} ? {b(cd)na/n = 0} ? {b(cd)nb/n = 0}
d. {acndnb|n = 1}
Ans: C
19.baa*c denotes the set
a. {bnamcp|n, m, p = 1}
b. {banc|n = 0}
c. {banc|n = 1}
d. {w|w is a string of a, b, c}
Ans: C
20. The set of all strings over the alphabet S = {a, b} (including e) is denoted by
a. (a + b)*
b. (a + b)+
c. a+b+
d. a*b*
Ans: A
21. Palindromes can’t be recognized by any FSA because
a. FSA cannot remember arbitrarily large amount of information
b. FSA cannot deterministically fix the midpoint
c. Even if the mid point is known an FSA cannot find whether the second half of the string matches the
first half
d. all of the above
Ans: D
22.Let S = {a, b, c, d, e}. The number of strings in S* of length 4 such that no symbol is used more than
once in a string is
a. 360
b. 120
c. 35d. 36
Ans: B
23.Which of the following denotes Chomskian hiearchy?
a. REG ? CFL ? CSL ? type0
b. CFL ? REG ? type0 ? CSL
c. CSL ? type0 ? REG ? CFL
d. CSL ? CFL ? REG ? type0
Ans: A
24.A language L is accepted by a FSA iff it is
a. CFL
b. CSL
c. recursive
d. regular
Ans: D
25.Which of the following regular expressions denotes a language comprising of all possible strings over
S = {a, b} of length n where n is a multiple of 3.
a. (a + b + aa + bb + aba + bba)*
b. (aaa + bbb)*
c. ((a + b)(a + b)(a + b))*
d. (aaa + ab + a) + (bbb + bb + a)
Ans: C
26.A language is represented by a regular expression (a)*(a + ba). Which of the following string does not
belong to the regular set represented by the above expression.
a. aaa
b. aba
c. ababad. aa
Ans: C
27.Which of the following is not primitive recursive but partially recursive?
a. McCarthy’s function
b. Riemann function
c. Ackermann’s function
d. Bounded function
Ans: C
28.Consider the following right-linear grammar G = (N, T, P, S) N = {S}
P : S ? aS|aA T = {a, b}
A ? bA|b
Which of the following regular expression denotes L(G)?
a. (a + b)*
b. a(ab)*b
c. aa*bb*
d. a*b*
Ans: C
29.Which of the following strings is not generated by the following grammar? S ? SaSbS|e
a. aabb
b. abab
c. aababb
d. aaabb
Ans: D
31.Consider a language L for which there exists a Turing machine TM, T, that accepts every word in L and
either rejects or loops for every word that is not in L. The language L is
a. NP hard
b. NP complete
c. recursive
d. recursively enumerable
Ans: D
32.Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?
a. I only
b. I and II
c. I and III
d. II and III
Ans: B
33.Which of the following statement is wrong?
a. Any regular language can be generated by a context-free grammar
b. Some non-regular languages cannot be generated by any CFG
c. the intersection of a CFL and regular set is a CFL
d. All non-regular languages can be generated by CFGs.
Ans: D
34.Recursively enumerable languages are not closed under
a. union
b. homomorphism
c. complementation
d. concatenation
Ans: C
35.Which of the following problem is undecidable?
a. membership problem for CFL
b. membership problem for regular sets
c. membership problem for CSL
d. membership problem for type 0 languages
Ans: D
36.Recursive languages are
a. a proper superset of CFL
b. always recognized by PDA
c. are also called type 0 languages
d. always recognized by FSA
Ans: A
37.R1 and R2 are regular sets. Which of the following is not true?
a. R1 n R2 neet not be regular
b. S* – R1 is regular
c. R1 ? R2 is regular
d. is regular
Ans: A
38.Which of the following regular expression identity is true?
a. r(*) = r*
b. (r*s*)* = (r + s)*
c. (r + s)* = r* + s*
d. r*s* = r* + s*
Ans: B
39.Which one of the following statement is FALSE?
a. context-free languages are closed under union
b. context-free languages are closed under concatenation
c. context-free languages are closed under intersection
d. context-free languages are closed under Kleene closure
Ans: C
40.Which of the following conversion is not possible (algorithmically)?
a. regular grammar to context-free grammar
b. nondeterministic FSA to deterministic FSA
c. nondeterministic PDA to deterministic PDA
d. nondeterministic TM to deterministic TM
Ans: C
BEST OF LUCK
No comments:
Post a Comment