Here are 60+ most important TOC mcq sppu and also contains Theory of computation mcq with answers pdf to free download. The toc sppu mcqs are most probably will get asked into your online exams. Best Luck.
Q.no 1. Which of the following does not belong to the language if input alphabet set is
a,b
A : a
B : b
C : epsilon
D : c
c
Q.no 2. Which of the following regular expressions represents the set of strings which
do not contain a substring ‘rt’ if alphabet = {r, t}
A : (rt)*
B : (tr)*
C : (rt)
D : (tr)
(tr)
Q.no 3. If there exists a language L, for which there exists a TM, T, that accepts every
word in L and either rejects or loops for every word that is not in L, is called
A : Recursive
B : Recursively Enumerable
C : NP-HARD
D : NP Complete
Recursively Enumerable
Q.no 4. Recursive languages are also known as:
A : decidable
B : Undecidable
C : sometimes decidable
D : infinite
decidable
Q.no 5. Which of the production rule can be accepted by Chomsky grammar. (i) A->BC,
(ii) A->a
A : only i
B : only ii
C : both i and ii
D : neither i nor ii
neither i nor ii
Q.no 6. Which of the following is true?
A : Every subset of a regular set is regular
B : Every finite subset of non-regular set is regular
C : The union of two non regular set is not regular
D : Infinite union of finite set is regular
Every finite subset of non-regular set is regular
Q.no 7. A push down automata is different than finite automata by
A : Its memory
B : number of states
C : start state
D : input symbols
Its memory
Q.no 8. Turing machine is more powerful than (a) Finite automata, (b) Push down
automata
A : Only (a)
B : Only (b)
C : Both (a) and (b)
D : Neither (a) nor (b)
Both (a) and (b)
Q.no 9. Turing machine was invented by
A : Alan Turing
B : Turing man
C : Turing taring
D : Turling Bake
Alan Turing
Q.no 10. Construct a regular expression for the language that contains strings having at
least one pair of consecutive zeros over {0, 1}.
A : (100)*
B : 1* (00)* 1*
C : [ (1 + 0 )* (00) (1 + 0 )] +
D : ((0+1)(0+1))
[ (1 + 0 )* (00) (1 + 0 )] +
Q.no 11. Why Palindromes cannot be recognized by any FSM ?
A : an FSM cannot deterministically fix the mid-point
B : an FSM can remember arbitrarily large amount of information
C : FSM has finite memory
D : FSM has only 5 tuples
an FSM cannot deterministically fix the mid-point
Q.no 12. is the class of decision problems that can be solved by nondeterministic polynomial algorithms?
A : NP
B : P
C : Hard
D : Complete
NP
Q.no 13. NPDA stands for
A : non deterministic pushup automata
B : null pushdown automata
C : nested pushdown automata
D : non deterministic pushdown automata
non deterministic pushdown automata
Q.no 14. A Turing machine with several tapes in known as
A : Multi-tape Turing machine
B : Poly-tape Turing maching
C : Universal Turing machine
D : Complete Turing machine
Multi-tape Turing machine
Q.no 15. If P, Q, R are three regular expressions and if P does not contain epsilon, then
the equation R = Q + RP has a unique solution given by
A : R = QP*
B : R = PQ
C : R = RP
D : R = QP
R = QP*
Q.no 16. Which among the following are incorrect regular identities?
A :
B :
C :
D :
D :
Q.no 17. Which of the following are the actions that operates on stack top?
A : only push
B : only pop
C : only push and pop
D : push, pop and replace
push, pop and replace
Q.no 18. A deterministic Turing machine is
A : Ambiguous Turing Machine
B : Unambiguous Turing Machine
C : Non-Deterministic Finite Automata
D : Deterministic Finite Automata
Unambiguous Turing Machine
Q.no 19. Bottom-up parsers use
A : leftmost derivation
B : rightmost derivation
C : rightmost derivation in reverse order
D : leftmost derivation in reverse order
rightmost derivation in reverse order
Q.no 20. A language L is said to be ___ if there is a turing machine M such that
L(M)=L and M halts at every point.
A : Turing acceptable
B : Decidable
C : Undecidable
D : NP-HARD
Decidable
Q.no 21. Which of the given problems are NP-complete?
A : (a) Traveling Salesman Problem
B : (b) Satisfiability Problem
C : Both (a) and (b)
D : Turing Machine
Both (a) and (b)
Q.no 22. The production of the form A->B , where A and B are non terminals is called
A : Null production
B : Greibach Normal Form
C : Unit production
D : Chomsky Normal Form
Unit production
Q.no 23. Which of the regular expressions corresponds to the given problem statement
over the alphabet = {a, b}, All strings in which the total number of a’s is divisible by 2.
A : ((a+b)(a+b))
B : (a + ab)*
C : ( b* a bab)* + b*
D : a* b (aa)b a
( b* a bab)* + b*
Q.no 24. Which of the following statement(s) are correct? (a) All languages can be
generated by CFG, (b) Any regular language has an equivalent CFG, (c) Some non
regular languages cannot be generated by CFG.
A : only (a)
B : Only (b)
C : Only (c)
D : Both (b) and (c
Both (b) and (c
Q.no 25. A grammar G=(V,T,P,S) in which V represents
A : Set of Nonterminals
B : Start symbol
C : Set of terminals
D : Production
Set of Nonterminals
Q.no 26. A PDA chooses the next move based on
A : current State and input
B : current state, stack and input
C : current state and stack
D : current state
current state, stack and input
Q.no 27. In multi head Turing machine there are
A : More than one heads of the Turing machine
B : More than one input tapes of Turing machine
C : Similar to the basic model of Turing machine
D : More than one input symbols of Turing machine
More than one heads of the Turing machine
Q.no 28. Construct a regular expression for the language that contains strings having
no pair of consecutive zeros over {0, 1}.
A : (1+0)*
B :
C : ((0+1)(0+1))*
D : (01 + 10)*
B :
Q.no 29. The difference between number of states in FA for regular expression (a + b)
and (a + b) * is:
A : 1
B : 2
C : 3
D : 0
1
Q.no 30. Which of the following statement is false?
A : Context free language is the subset of context sensitive language
B : Regular language is the subset of context sensitive language
C : Recursively ennumerable language is the super set of regular language
D : Context sensitive language is a subset of context free language
Atomicity Context sensitive language is a subset of context free language
Q.no 31. Which among the following is the LEAF of the parse tree?
A : Production P
B : Nonterminal V
C : Terminal T
D : Starting symbol S
Terminal T
Q.no 32. The ability for a system of instructions to simulate a Turing Machine is called
A : Turing Completeness
B : Simulation
C : Turing Halting
D : Computability
Turing Completeness
Q.no 33. Which of the following statement is false?
A : Every language that is defined by regular expression can also be defined by finite
automata
B : Every language defined by finite automata can also be defined by regular expression
C : We can convert regular expressions into finite automata
D : There exists a unique DFA for every regular language
Atomicity D : There exists a unique DFA for every regular language
Q.no 34. Which of the following statements is false?
A : For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.
B : Turing recognizable languages are closed under union and complement.
C : Turing decidable languages are closed under intersection
and complement.
D : Turing recognizable languages are closed under union and intersection.
AtomicityTuring recognizable languages are closed under union and complement.
Q.no 35. How many strings of length less than 4 contain the language described by the
regular expression (x+y)y(a+ab)
A : 7
B : 10
C : 12
D : 11
12
Q.no 36. An instantaneous description of Turing machine consists of
A : Present state and input to be processed
B : Present state and entire input to be processed
C : Present input only
D : Present state only
Present state and entire input to be processed
Q.no 37. According to the given language, which among the following expressions does
it corresponds to Language L={xϵ{0,1}|x is of length 4 or less}
A : (0+1+0+1+0+1+0+1)^4
B : (0+1)^4
C : (01)^4
D : (0+1+ε)^4
(0+1+ε)^4
Q.no 38. Identify the following problem: If G=(V, E) and V’ is subset of V, then V’ is an
independent set iff no two nodes in V’ are connected by an edge in E.
A : Satisfiability
B : Independent set
C : Node-Cover Problem
D : Traveling Salesman Problem
Independent set
Q.no 39. Which of the following is analogous to the NFA and NPDA ?
A : Regular language and Context Free language
B : Regular language and Context Sensitive language
C : Context free language and Context Sensitive language
D : Unrestricted language
Regular language and Context Free language
Q.no 40. Given grammar G:
(1)S->AS (2)S->AAS (3)A->SA (4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
A : 2,4
B : 1,3
C : 1, 2, 3, 4
D : 2, 3, 4
2,4
Q.no 41.
A : X is decidable
B : X is undecidable but partially decidable
C : X is undecidable and not even partially decidable
D : X is not a decision problem
X is undecidable but partially decidable
Q.no 42.
A : A
B : B
C : C
D : D
B
Q.no 43. The language generated by
S-> aSa|bSb|a|b
over the alphabet {a,b} is the set of
A : All length palindrome
B : Even length palindrome
C : Odd length palindrome
D : Strings starting and ending with different character
Odd length palindrome
Q.no 44. John is asked to make an automaton which accepts a given string for all the
occurrence of ‘1001’ in it. How many number of transitions would John use such that,
the string processing application works?
A : 10
B : 11
C : 12
D : 15
10
Q.no 45. The context free grammar
S->SS|0S1 |1S0|Є
generates :
A : Unequal number of 0’s and 1’s
B : Equal number of 0’s and 1’s
C : Any number of 0’s followed by any number of 1’s
D : 0’s followed by 1’s
Equal number of 0’s and 1’s
Q.no 46. Which of the following will not be accepted by the following DFA?
A : ababaabaa
B : abbbaa
C : abbbaabb
D : abbaabbaa
ababaabaa
Q.no 47. Consider three decision problems P1, P2 and P3. It is known that P1 is
decidable and P2 is undecidable. Which one of the following is True?
A : P3 is decidable if P1 is reducible to P3
B : P3 is undecidable if P3 is reducible to P2
C : P3 is undecidable if P2 is reducible to P3
D : P3 is decidable if P3 is reducible to P2’s complement
P3 is undecidable if P2 is reducible to P3
Q.no 48. Transition function of NFA machine is given by
A :
B :
C :
D :
D :
Q.no 49. Which grammar accepts the language of {a, b} having strings ending with ‘a’.
A : S->aS | bS
B : S->aS | bS |b
C : S->aS | bS |S
D :c
S->aS | bS |a
Q.no 50. The following Turing machine acts like
A : Copies a string
B : Delete a symbol
C : Insert a symbol
D : Push the symbol
Delete a symbol
Q.no 51. Find the pair of regular expressions that are equivalent
A : (0+1)* and (01)*
B : (0+10)* and (0+10)
C : (0+10) and (0+10)
D : (111) and (111+11)
(0+10) and (0+10)
Q.no 52. Which Transition table of Turing Machine is correct to check well formedness
of parentheses?
A :
B :
C :
D :
A :
Q.no 53. Which of the following statement is false.
A : There exist context-free languages such that all context free grammars generating them
are ambiguous.
B : An unambiguous context free grammar always has a unique parse tree for each string of
the language generated by it.
C : Both deterministic and non deterministic PDA always accet same set of languages.
D : Finite set of strings from one alphabet is always a regular language.
Both deterministic and non deterministic PDA always accet same set of languages.
Q.no 54. The language A-> tB|t generated by which of the following grammar?
A : Type 3
B : Type 2
C : Type 1
D : Type 0
Type 3
Q.no 55. Which Transition Diagram is correct for the following problem
“Design a TM that erases all non blank symbols on the tape, where the sequence of nonblank symbols does not contain any blank symbols B in between. Consider Alphabet
{a,b}.
A :
B :
C :
D :
A :
Q.no 56. For two regular 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
b (a + b ) * a
Q.no 57. Consider the following statements.
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are true?
A : Only II
B : Only III
C : Only I and II
D : Only I and III
Only I and IIIy
Q.no 58. Which Transition table of Turing Machine is correct for the following problem
“Design a TM to find 2’s complement of a binary number”.
A :
B :
C :
D :
B :
Q.no 59.
A : X is undecidable but partially decidable
B : X is decidable
C : X is not a decision problem
D : X is undecidable and not even partially decidable.
X is undecidable but partially decidable
Q.no 60. The minimum number of productions required to produce a language
consisting of palindrome strings (even and odd length) over T={a,b} is
A : 3
B : 5
C : 7
D : 2
Atomicity
theory of computation mcq sppu, theory of computation mcq with answers pdf, toc mcq sppu, toc sppu mcq, toc mcq questions