Theory Of Computation MCQ 1
This page is provided with simple multiple choice questions in Theory of computation.
If the reader want to learn all the concepts of theory of computation. Click Here.
At learning monkey one can learn all the computer science subjects from basics to advanced and GATE for free. Click Here.
1) All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
1) i, ii, iv
2) i, ii, iii
3) i, iv
4) i, ii, iii, iv
Answer: 4
2) Which of the technique can be used to prove that a language is non regular?
1) Ardens theorem
2) Pumping Lemma
3) Ogden’s Lemma
4) None of the mentioned
Answer: 2
3) Which of the following language regular?
1) {aibi|i>=0}
2) {aibi|0<i<5}
3) {aibi|i>=1}
4) None of the mentioned
Answer: 2
4) Which of the following are non regular?
1) The set of strings in {a,b}* with an even number of b’s
2) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
3) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.
4) None of the mentioned
Answer: 4
5) If L is DFA-regular, L’ is
1) Non regular
2) DFA-regular
3) Non-finite
4) None of the mentioned
Answer: 2
6) Myhill Nerode does the following:
1) Minimization of DFA
2) Tells us exactly when a language is regular
3) Both (a) and (b)
4) None of the mentioned
Answer: 3
7) Which of the following options is incorrect?
1) A language L is regular if and only if ~L has finite number of equivalent classes.
2) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognises L must have at most k states.
3) A language L is NFA-regular if and only if it is DFA-regular.
4) None of the mentioned
Answer: 2
8) Which of the following are related to tree automaton?
1) Myphill Nerode Theorem
2) State machine
3) Courcelle’s Theorem
4) All of the mentioned
Answer: 4
9) Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
1) i, iii
2) i
3) iii
4) i, ii, iii
Answer: 4
10) Finite state machine are not able to recognise Palindromes because:
1) Finite automata cannot deterministically find the midpoint
2) Finite automata cannot remember arbitrarily large amount of data
3) Even if the mid point is known, it cannot find whether the second half matches the first
4) All of the mentioned
Answer: 4
11) Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.
1) Turing Machine
2) Pumping Lemma
3) Arden’s theorem
4) None of the mentioned
Answer: 2
12) While applying Pumping lemma over a regular language, we consider a string w that belong to L and fragment it into _________ parts.
1) 2
2) 5
3) 3
4) 6
Answer: 3
13) If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
1) x
2) y
3) z
4) all of the mentioned
Answer: 2
14) Let w= xyz and y refers to the middle portion and |y|>0.What do we call the
process of repeating y 0 or more times before checking that they still belong to the language L or not?
1) Generating
2) Pumping
3) Producing
4) None of the mentioned
Answer: 2
15) There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n
for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
1) n
2) |y|
3) |x|
4) none of the mentioned
Answer: a
16) Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
1) p*1
2) p+1
3) p-1
4) None of the mentioned
Answer: 2
17) Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Ф represents the language that consist of no string.
1) Statement 1 and 2 both are correct
2) Statement 1 is false but 2 is correct
3) Statement 1 and 2 both are false
4) There is no difference between both the statements, ε and Ф are different notation for same reason
Answer: 1
18) The appropriate precedence order of operations over a Regular Language is
1) Kleene, Union, Concatenate
2) Kleene, Star, Union
3) Kleene, Dot, Union
4) Star, Union, Dot
Answer: 3
19) Regular Expression R and the language it describes can be represented as:
1) R, R(L)
2) L(R), R(L)
3) R, L(R)
4) All of the mentioned
Answer: 3
20) Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
1) {w | w is a string of odd length}
2) {w | w is a string of length multiple of 3}
3) {w | w is a string of length 3}
4) All of the mentioned
Answer: 2