THEORETICAL COMPUTER SCIENCE
Practice MCQ
1. Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?
a. a*b*
b. (a|b)*
c. (ab)+
d. (a|b*)
Answer :b
2. Regular expression a|b denotes the set
a) {a}
b) {€,a,b}
c) {a,b}
d) {ab}
Answer :c
a) Designing computers
b) Designing compilers
c) Both (a) and (b)
d) Developing computers
Answer :c
4. Which of the following regular expression denotes zero or more instances of
an a or b?
a) (a|b)
b) (ab)*
c) (a|b)*
d) a*|b
Answer :b
5. Idempotent law is ..................
a) ꬾ+L=L
b) €L=L€=L
c) (L*)*=L*
d) L+L=L
Answer :d
6. Which of the following regular expressions denotes a language comprising
all possible strings of even length over the alphabet (0,1)?
a) (0|1)*
b) (0|1)(0|1)*
c) (00|01|10|11)*
d) (0|1)(0|1)(0|1)*
Answer :c
7. The regular sets are closed under
a) Union
b) Concatenation
c) Kleene closure
d) All of these
Answer :d
8. If a and b be the regular expressions,then (a* ᴗb*)* is equivalent to
a) (aᴗb)*
b) (b*ᴗa*)*
c) (bᴗa)*
d) (aᴗb)
Answer :a
9. Which of the following RE 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)*
Answer :c,d
10.Two of the following four Res are equivalent .Which two is the empty
string?
I. (00)*( €+0)
II. (00)*
III. 0*
IV. 0(00)*
Codes:
a) I and II
b) II and III
c) I and III
d) III and IV
Answer :c
11.The languages of all words with at least 2 a’s can be described by the regular
expression
a) (ab)*a and a(ba)*
b) (a+b)* ab* a(a+b)*
c) b* ab* a (a+b)*
d) all of these
Answer :d
12. Given the language L={ab,aa,baa},which of the following string are in L*?
I. abaabaaabaa
II. aaaabaaaa
III. baaaaabaaaab
IV. baaaaaba
Codes:
a) I,II and III
b) II.III and IV
c) I,II and IV
d) I,III and IV
Answer :c
13.The regular expression (a|b)*denotes the set of all strings
a) With 0 or more instance of a or b
b) With one or more instance of a or b
c) Equal to regular expression (a*b*)*
d) Both (a) and (c)
Answer :d
14.If R1 and R2 be regular sets defined over the alphabet ∑,then
a) R1∪ R2 is not regular
b) R1 ∩ R2 is regular
c) ∑* - R1 is regular
d) Both (a) and (b)
Answer :d
15.If L be set of strings from alphabet ,then Kleene closure of L is given as
a) L+=Ui=0 Li
b) L*=Ui=0Li
c) L*=Ui=0∞ Li
d) L+=Ui=1Li
Answer :b
16.Can a DFA simulate NFA?
a) No
b) Yes
c) Sometimes
d) Depends on NFA
Answer :b
17.An automation is a...............device and a grammar is a ..........device
a) Generative, cognitive
b) Generative, acceptor
c) Acceptor, cognitive
d) Cognitive, generative
Answer :d
18.The major difference between a Moore and Mealy machine is that
a) Output of the former depends on the present state and present input
b) Output of the former depends only on the present state
c) Output of former depends only on the present input
d) All of these
Answer :b
19.Two finite state machines are said to be equivalent if they
a) Have same number of states
b) Have same number of edges
c) Have same number of states and edges
d) Recognize same set of tokens
Answer :c
20.Which of the following statement is false?
a) Every NFA can be converted to an equivalent DFA
b) Every non-deterministic TM can be converted to an equivalent
deterministic TM
c) Every regular language is also a context –free language
d) Every subset of a recursively enumerable set is recursive
Answer :d
21.Transition function(⸹) of NFA
a) QX∑→2Q
b) QX∑→Q
c) QX∑→2QN
d) QX∑→ג
Answer :a
22.Tuples of є-NFA
a) (Q, ∑,⸹,q0,F)
b) (Q, ∑U{ є},⸹,q0,F)
(Q, ∑,ג,q,F)
c) (Q,V,P,S)
Answer :b
23.NFA,in its name has ‘non-deterministic’ because of:
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the above.
Answer :b
24.Myhill Nerode theorem is used for
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) Conversion of NFA to DFA
Answer :a
25. Language of finite automata is generated by
a) Type 0 grammar
b) Type 1 grammar
c) Type 2 grammar
d) Type 3 grammar
Answer :d
26.Which of the following are the examples of finite state machine system
a) Traffic lights
b) Combinational circuits
c) Digital watches
d) Both (a) and (b)
Answer :d
27.Backtracking is allowed in
a) NDFA
b) DFA
c) Both (a) and (b)
d) e-NFA
Answer :b
28.є -closure of state is combination of self state and ........
a) є -reachable states
b) initial states
c) final state
d) all
Answer :a
29.In moore machine is of length n then output string length will be
a) n+1
b) n
c) n+n
d) 2n
Answer :a
30.Mealy machine and Moore machine is also called
a) TM
b) LBA
c) Transducer
d) PDA
Answer :c
31.Regular sets are closed under
a) union
b) concatenation
c) Kleen closure
d) All of the above
Answer :d
32.For each Regular Expression there exist .............
a) FA
b) RE
c) Union
d) Kleen closure
Answer :a
33.(a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) ab*
Answer :b
34.Regular Expression for the following DFA
a) r=є
b) r=(a+b)*
c) r=a+b
d) r=a
Answer :b
35.What can be said about a regular language L over {a} whose minimal finite
state has two states?
a) L must be {an| n is odd}
b) L must be {an|n is even}
c) L must be {an|n≥0}
d) Either L must be {an| n is odd},or L must be {an| n iseven}
Answer :d
36.Choose the correct statement
a) L={anbncn| n=1,2,3.... } is recursively enumerable
b) Recursive languages are closed under union
c) Both (a) and (b)
d) Recursive languages are closed under intersection
Answer :c
37.The languages of all words (made up of a’s and b’s)with at least 2a’s can be
described by the regular expression
a) (a+b)*a(a+b)*a(a+b)*
b) (a+b)*ab*a(a+b)*
c) b*ab*a(a+b)*
d) all of these
Answer :d
38.Consider two languages L1=(a+b)*a and L2=b(a+b)*.The intersection of L1
and L2 is given by
a) (a+b)*ab
b) ab(a+b)*
c) a(a+b)*b
d) b(a+b)*a
Answer :d
39.Which language is regular from the following
a) L={aibjck|k>i+j}
b) L={ww| w є {a,b}*}
c) L={a2n|n≥1}
d) L={anbnan}
Answer :c
40.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)*
Answer :c
41.Which one of the following languages over the alphabet {0,1} is described
by the regular expression: (0+1)*0(0+1)*0(0+1)*?
a) The set of all strings containing the substring 00
b) The set of all strings containing at most 2 zeros
c) The set of all strings containing at least 2 zeros
d) The set of all strings starts with zero and end with zero
Answer :c
42.Consider the following DFA which of the following is TRUE?
a) It only accepts the strings with prefix as “aababb”
b) It only accepts the string with substring as “aababb”
c) It only accepts the strings with suffix “aababb”
d) It only accepts the strings starts with ‘b’
Answer :b
43.The following finite automation recognizes which of the given languages?
a) {1,0}*{01}
b) {1,0}*{1}
c) {1}{1,0}*{1}
d) 1*0*{0,1}
Answer :a
44.Pumping lemma for regular language is generally used for proving:
a) Whether two given regular expressions are equivalent
b) A given grammar is ambiguous
c) A given grammar is regular
d) A given grammar is not regular
Answer :d
45.A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
Answer :a
46.Finite state machine can recognize
a) any grammar
b) only CFG
c) any unambiguous grammar
d) only regular grammar
Answer :d
47.The ‘C’ language is
a) Context free language
b) Context sensitive language
c) Regular language
d) Recursively enumerable language
Answer :a
48.In a Context free grammar
a) Epsilon can’t be the right hand side of any production
b) Terminal symbols can’t be present in the left hand side of any
production
c) Number of grammar symbols in the left hand side is not greater than
the number of grammar symbols in the right hand side
d) All of these
Answer :d
49.A grammar that produces more than one parse tree for same sentence is
called
a) Ambiguous
b) Regular
c) Unambiguous
d) CFG
Answer :a
50.Consider a grammar:
G=({x,y},{S,x,y,z},p,S)
Where elements of parse:
S→xy
S→yx
x→xz
x→x
y→y
z→z
the language L generated by G most accurately is called
a) Chomsky type 0
b) Chomsky type 1
c) Chomsky type 2
d) Chomsky type 3
Answer :d
51.The set {anbn|n=1,2,3........}can be generated by the CFG
a) S→ab|aSb
b) S→aaSbb|ab
c) S→ab|aSb|E
d) S→aaSb|ab|aabb
Answer :a,d
52.Consider the grammar
S→ABCc|Abc
BA→AB
Bb→bb
Ab→ab
Aa→aa
which of the following sentence can be derived by this grammar?
a) abc
b) abcc
c) aab
d) abbc
Answer :a
Quiz Coming soon...
1 Comments
Wpersmites_n Sarah Thomas https://wakelet.com/wake/VwG-yC2oIuoIMFkexkezC
ReplyDeletefiapicpolstech
Thanks,To visit this blog.