Instructions:
(a)4 marks will be allotted for correct question and 1 will be
deducted for incorrect question. (b)More than
one answer can be correct.
Que.
1
Context-free languages are closed under:
A
Union , intersection
B
Union , Kleene closure
C
Intersection, complement
D
Complement, Kleene Closure
Que.
2
Let L p be the set of all languages accepted by a PDA by final
state and L E the set of all languages accepted by empty stack.
Which of the following is true?
A
L D = L E
B
L D É L E
C
L D = L E
D
None of the above
Que.
3
A grammar that is both left and right recursive for anonterminal,
is
A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or
(D)None of the above
D
(C)Information is not sufficient to decide whether it is ambiguous or
None of the above
Que.
4
Let S and T be languages over S = {a, b} represented by the regular expressions (a + b *) * and (a + b) *, respectively. Which of the following is true?
A
S Ì T
B
T Ì S
C
S = T
D
S Ç T = f
Que.
5
Let L denotes the language generated by the grammar S->0S0/00.
Which of the following is true?
A
L = 0 +
B
L is regular but not 0 +
C
L is context free but not regular
D
L is not context free
Que.
6
Which of the following need not necessarily be saved on a context switch
between processes?
A
General purpose registers
B
Translation look aside buffer
C
Program counter
D
All of the above
Que.
7
Given an arbitrary non-deterministic finite automaton (NFA) with
N states, the maximum number of states in an equivalent minimized
DFA is at least
A
N^2
B
2^N
C
2N
D
N!
Que.
8
Which one of the following regular expression over {1,1} denotes the set of all strings not containing 100 as a substring?
A
0*(1+0)*
B
0*1010*
C
0*101
D
0*(10+1)*
Que.
9
Aliasing in the context of programming languages refers to
A
multiple variables having the same memory location
B
multiple variables having the same value
C
multiple variables having the same identifier
D
multiple uses of the same variable
Que.
10
Consider the following decision problems : (PI) Does a given finite
state machine accept a given string (P2) Does a given context free grammar
generate an infinite number of stings Which of the following statements
is true?
A
Both (PI) and (P2) are decidable
B
Neither (PI) nor (P2) are decidable
C
Only (PI) is decidable
D
Only (P2) is decidable
Que.
11
Given the following expression grammar:
E->E * F | F+E | F
F-> F-F | id
Which of the following is true?
A
* has higher precedence than +
B
- has higher precedence than *
C
+ and - have same precedence
D
+ has higher precedence than *
Que.
12
Consider the following two statements:
S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language
Which of the following statements is correct?
A
Only S1 is correct
B
Only S2 is correct
C
Both S1 and S2 are correct
D
None of S1 andS2 is correct
Que.
13
Which of the following statements in true?
A
If a language is context free it can always be accepted by a deterministic
push-down automaton
B
The union of two context free languages is context free
C
The intersection of two context free languages is context free
D
The complement of a context free language is context free
Que.
14
Which of the following statements is false?
A
An unambiguous grammar has same leftmost and rightmost derivation
B
An LL(1) parser is a top-down parser
C
LALR is more powerful than SLR
D
An ambiguous grammar can never be LR(k) for any k
Que.
15
Consider the following languages:
L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}
Which of the languages are regular?
A
Only L1 and L2
B
Only L2, L3, and L4
C
Only L3 and L4
D
Only L3
Que.
16
Context free language are closed under
A
union, intesection
B
union,kleene closure
C
intesection,complement
D
complement,kleene closure
Que.
17
Context free languages are
A
closed under union
B
closed under complementation
C
closed under intersection
D
all of the above
Que.
18
Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
Que.
19
Type O grammer is
A
(C)both and (b) above
B
(C)both (a) and above
C
both (a) and (b) above
D
none of these
Que.
20
Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A
8
B
14
C
15
D
48
Que.
21
The language L={(a^k)(b^k) | k>or= 1} is
A
type 3 grammer
B
type 2 grammer
C
type 1 grammer
D
type 0 grammer
Que.
22
Recursive languages are
A
a proper superset of context free languages
B
always recognizable by pushdown automata
C
also called type zero lanugages
D
all of these
Que.
23
A grammer that is both left and right recursive for a nopn-terminal is
A
ambiguous
B
unambiguous
C
information is not sufficient to decide whether it is ambiguous or
unambiguous
D
none of the above
Que.
24
For what values of n is 10*n*log2 (n) >2*(n^2)?
A
only n>/= 32
B
only 0
C
only 20
D
only n>/=0
Que.
25
Let * be defined as x*y = x' + y.Let z = x * y .Value of z*x is
A
x' + y
B
x
C
0
D
1
Que.
26
Which of the following regular expressions over {0,1} denotes the set of all strings not containing
100 as a substring
A
0*(1+0)*
B
0*1010*
C
0*1*01*
D
0*(10+1)*
Que.
27
Which of the following grammer rules violate the requirements of an operator
grammer? P,Q,R are nonterminals and r,s,t are terminals. (i)
P -> Q R (ii) P -> QsR (iii) P -> e (iv)P
->Qtpr
A
(i) only
B
(i) and (iii) only
C
(ii) and (iii) only
D
(iii) and (iv) only
Que.
28
indicate which ofthe following statments are true Recursive language
are
A
A proper superset of context free languages
B
always recognizable by pushdown automata
C
recognizable by turing machine
D
also called type-0 languages
Que.
29
Which of the following is not decidable?
A
Given a Turing machine M,a string s and an integer k,M accepts s
within k steps
B
Equivalence of two given Turing machines
C
Language Accepted by a given finite state machine is not empty
D
language generated by a context free grammer is not empty
Que.
30
Regarding the power of recognition of languages,Which of the following
statments is false?
A
the non-deterministic finite-state automata are equivalent to deterministic
finite state automata.
B
non-deterministic push down automata are equivalent to deterministic
push down automata.
C
non-deterministic Turing machines are equivalent to deterministic
to push down automata.
D
non-deterministic Turing machines are equivalent to deterministic
Turing machines
Que.
31
The string 1101 does not belong to the set represented by
A
110*(0+1)
B
1(0+1)*101
C
(10)*(01)*(00+11)*
D
(00+(11)*0)*
Que.
32
The following grammer
S->bS S->b S->aA A->bA
A->aB B->bB B->aS
B->a is
A
type 3 grammer
B
type 2 grammer
C
type 1 grammer
D
type 0 grammer
Que.
33
A language accepted by a pushdown Automaton in which the stack is limited
to 10 items is best described as
A
Context free
B
Regular
C
Deterministic Context free
D
Recursive
Que.
34
Aliasing in the context of programming languages refers to
A
multiple variables having the same memory location
B
multiple variables having the same value
C
multiple variables having the same identifier
D
multiple uses of the same variable
Que.
35
If L1 is context free language and L2 is aregular language which ofthe
followingi/are false
A
L1-L2 is not context free
B
L1 (intersection) L2 is context free
C
~L2 is context free
D
~L1 isregular
Que.
36
consider the following regular expression :
R=(ab|abb)*bbab
Which of the following strings is NOT in the set denoted by R?
A
ababab
B
abbbab
C
abbabbbab
D
ababbabbbab
Que.
37
The following grammar
S->bS S->b S->aA A->bA is
A
type-3 grammer
B
type-2 grammer
C
type-1 grammer
D
type-0 grammer
Que.
38
The smallest finite aitomaton which accepts the language {x|length of x is divisible by 3} has
A
2 states
B
3 states
C
4 states
D
5 states
Que.
39
The following production A -> ab A -> aA aAb ->
aBCb is
A
type-3 grammer
B
type-2 grammer
C
type-1 grammer
D
type-0 grammer
Que.
40
Which of the following statment is false>
A
every finite subset of an non-regular set is regular
