MCQ | Theory of Computation (TOC) Part 1

Theory of Computation - TOC

« Previous Next »

1. That finite automata which does not contain any ambiguity is called

A) DFA
B) NDFA
C) PDA
D) Regular Expression

... Answer is A)
DFA

2. Machine without output

A) DFA
B) Meely machine
C) Moore machine
D) All of these

... Answer is A)
DFA

3. PDA is a set of _____ tupples

A) 7
B) 4
C) 6
D) 2

... Answer is A)
7

4. Grammar ia s set of following tuples

A) (V,T,F,S)
B) (Q,T,P,S)
C) (V,T,P,S)
D) (M,T,P,S)

... Answer is C)
(V,T,P,S)

5. Construct a Regular Expression which accept string of 0's and 1's end with substring 00.

A) (0 + 1)* (100)
B) (1+0)* (10)
C) (0 + 1)* (00)
D) None of these

... Answer is C)
(0 + 1)* (00)

6. Construct a Regular Expression which accept string of a's and b's contain one a's and two b's

A) bb +bab +ba
B) abb +bab +bba
C) bbb +bab +bba
D) aab +bab +aba

... Answer is B)
abb +bab +bba

7. ε + 11* =

A) 1+ (1 positive closure)
B) 1* (kleen closure)
C) 1
D) 11

... Answer is A)
1+ (1 positive closure)

8. Which grammar is in GNF

A) S->AA|0 , A->SS|1
B) A->aB, B->b
C) A->aBd, B->b
D) None of these

... Answer is B)
A->aB, B->b

9.εεaεεbεcεε=

A) abc
B) ε
C) a
D) ab

... Answer is A)
abc

10.Moore Machine is an application of

A) Finite automata without input
B) Non Deterministic Finite automata with output
C) Finite automata with output
D) None of these

... Answer is C)
Finite automata with output

11. In Moore machine produce output over the change of

A) transitions
B) states
C) input symbol
D) None of these

... Answer is A)
transitions

12. Moore Machine produce output of length ______ for any input string

A) |Input-1|
B) |Input|+1
C) |Input|
D) |Input|-1

... Answer is B)
|Input|+1

13. "What is the output for the given language? Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)"

A) 10001
B) 101010
C) 111010
D) 10000

... Answer is A)
10001

14. In Moore machine output alphabet can be represented as:

A) ∑
B) δ
C) ∆
D) None of these

... Answer is C)
∆

15. Which of the following is a correct statement?

A) Moore machine has no final states
B) Mealy machine has final states
C) We can convert Mealy to Moore but not vice versa
C) All of these

... Answer is A)
Moore machine has no final states

16. In mealy machine, the O/P depends upon?

A) final state
B) state and input
C) state
D) input

... Answer is B)
state and input

17. The major difference between Mealy and Moore machine can be can be identify by

A) input
B) output
C) states
D) final state

... Answer is B)
output

18. The major difference between Mealy and Moore machine can be can be identify by

A) output
B) input
C) states
D) None of these

... Answer is A)
output

19. Which of the following does not belong to input alphabet if S={a, b}* for any language?

A) ε
B) a
C) ab
D) b

... Answer is A)
ε

20. The number of final states we need as per the given language? Language L: {an| n is even or divisible by 3}

A) 4
B) 1
C) 2
D) 3

... Answer is C)
2

21.A Language for which no DFA exist is a________

A) Non-Regular Language
B) Regular Language
C) May be Regular
D) None of these

... Answer is A)
Non-Regular Language

22. How we know 2 finite states are equivalent?

A) When same number of states
B) When same number of transitions
C) When same number of states as well as transitions
D) When Both are final states

... Answer is C)
When same number of states as well as transitions

23. Can a DFA recognize a palindrome number?

A) Yes, with input alphabet as ∑*
B) Yes
C) No
D) Can’t be determined

... Answer is C)
No

24. Let ∑= {a, b, …. z} and A = {TOC, Quiz}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:

A) {}
B) {Input, Output, ε}
C) {TOC, Quiz, ε}
D) {TOC, Quiz, Input, Output, ε}

... Answer is A)
{}

25. The language of all words with at least 2 0's can be described by the regular expression

A) 1* 01* 0 (0 + 1)*
B) (0 + 1)* 01* 0 (0 + 1)*
C) (01)*0 and 0 (10)*
D) All of these

... Answer is D)
All of these

26. The following CFG is in S -> aBB , B -> bAA , A -> a, B -> b

A) Greibach normal form
B) Weak Chomsky normal form but not Chomsky normal form
C) Strong Chomsky normal form
D) Chomsky normal form but not strong Chomsky normal form

... Answer is A)
Greibach normal form

27. In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of

A) Terminals on the right hand side
B) Grammar symbols on the right hand side
C) Non-terminals on the right hand side
D) None of these

... Answer is C)
Non-terminals on the right hand side

28. Which of the following denotes Chomskian hiearchy?

A) CSL -> CFL -> REG -> type0
B) REG -> CFL -> CSL -> type0
C) CFL -> REG -> type0 -> CSL
D) CSL -> type0 -> REG -> CFL

... Answer is B)
REG -> CFL -> CSL -> type0

29. A grammar that produces more than one parse tree for some sentence is called

A) Ambiguous
B) Regular
C) Unambiguous
D) None of these

... Answer is A)
Ambiguous

30. If R1 and R2 are the regular expressions denoting the languages L1 and L2 respectively, then which of the following is wrong?

A) φ is not a regular expression
B) (R1) .(R2) is a regular expression denoting L1​. L2
C) (R1) | (R2) is a regular expression denoting L1 ∪ L2
D) None of these

... Answer is A)
φ is not a regular expression

31. A language is represented by a regular expression (0)*(0 + 10). Which of the following string does not belong to the regular set represented by the above expression.

A) 000'
B) 010'
C) 1010
D) 00'

... Answer is C)
1010

32. Which of the following is true?

A) Every subset of a regular set is regular
B) The union of two non regular set is not regular
C) Every finite subset of non-regular set is regular
D) Infinite union of finite set is regular

... Answer is C)
Every finite subset of non-regular set is regular

33. A push down automata is different than finite automata by

A) start state
B) Its memory
C) input symbols
D) number of states

... Answer is B)
Its memory

34. Turing machine is more powerful than (a) Finite automata, (b) Push down

A) Only (b)
B) Only (a)
C) Both (a) and (b)
D) None of these

... Answer is C)
Only (b)

35. Turing machine was invented by

A) Turing taring
B) Turing man
C) Alan Turing
D) Turling Bake

... Answer is C)
Alan Turing

36. NPDA stands for

A) non deterministic pushup automata
B) nested pushdown automata
C) non deterministic pushdown automata
D) null pushdown automata

... Answer is C)
non deterministic pushdown automata

37. A Turing machine with several tapes in known as

A) Multi-tape Turing machine
B) Complete Turing machine
C) Universal Turing machine
D) Poly-tape Turing maching

... Answer is A)
Multi-tape Turing machine

38. 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) QP*
B) QP
C) PQ
D) RP

... Answer is A)
QP*

39. 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) Undecidable
C) Decidable
D) NP-HARD

... Answer is C)
Decidable

40. Which of the given problems are NP-complete?

A) Traveling Salesman Problem
B) Turing Machine
C) PDA
D) Regular Expression

... Answer is A)
Traveling Salesman Problem

41. A grammar G=(V,T,P,S) in which V represents

A) Set of terminals
B) Start symbol
C) Production
D) Set of non terminals

... Answer is D)
Set of non terminals

42. A PDA chooses the next move based on

A) current state, stack and input
B) current state and stack
C) current state
D) current State and input

... Answer is A)
current state, stack and input

43. The difference between number of states in FA for regular expression (a + b) and (a + b) * is:

A) 1
B) 2
C) 3
D) 4

... Answer is A)
1

44. Which among the following is the LEAF of the parse tree?

A) Terminal T
B) Nonterminal V
C) Starting symbol S
D) Production P

... Answer is A)
Terminal T

45. The ability for a system of instructions to simulate a Turing Machine is called

A) Turing Halting
B) Computability
C) Turing Completeness
D) Simulation

... Answer is C)
Turing Completeness

46. Which of the following statement is false?

A) We can convert regular expressions into finite automata
B) Every language defined by finite automata can also be defined by regular expression
C) There exists a unique DFA for every regular language
D) Every language that is defined by regular expression can also be defined by finite automata

... Answer is C)
There exists a unique DFA for every regular language

47. Identify the following problem: If G=(V, E) and V’ is subset of V, then V’ is an independent set if no two nodes in V’ are connected by an edge in E.

A) Independent set
B) Traveling Salesman Problem
C) Node-Cover Problem
D) Satisfiability

... Answer is A)
Independent set

48. Which one of the following languages over the alphabet {a,b} is described by the regular expression: (a+b)*a(a+b)*a(a+b)* ?

A) The set of all strings containing at most two a’s.
B) The set of all strings containing the substring aa.
C) The set of all strings containing at least two a’s.
D) The set of all strings that begin and end with either a or b.

... Answer is C)
The set of all strings containing at least two a’s.

49. Which one of the following is FALSE?

A) Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
B) Complement of every context-free language is recursive.
C) There is unique minimal DFA for every regular language
D) Every NFA can be converted to an equivalent PDA.

... Answer is A)
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

50.The regular expression a*(ba*)* denotes the same set as

A) (a + b)* ba(a + b)*
B) (b*a)*b*
C) (a*b)*b*
D) None of these

... Answer is B)
(b*a)*b*

51. Let S and T be language over Σ = {0,1} represented by the regular expressions (0+1*)* and (0+1)*, respectively. Which of the following is true?

A) S = T
B) S ⊂ T
C) T ⊂ S
D) S ∩ T = φ

... Answer is A)
S = T

52. How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's

A) 2
B) 3
C) 4
D) 5

... Answer is A)
2

53. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (a + b)*(ba) is ____________

A) 5
B) 4
C) 3
D) 6

... Answer is C)
3

54. The language accepted by a Push down Automata

A) Type0
B) Type1
C) Type2
D) Type3

... Answer is C)
Type2

55. Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is

A) context-free ⊂ right-linear ⊂ context-sensitive
B) context-free ⊂ context-sensitive ⊂ right-linear
C) context-sensitive ⊂ right-inear ⊂context-free
D) right-linear ⊂context-free ⊂context-sensitive

... Answer is D)
right-linear ⊂context-free ⊂context-sensitive

56. Which of the following CFG's can't be simulated by an FSM?

A) aSb | ab
B) Sa | b
C) abX, X --> cY, Y --> d | aX
D) None of these

... Answer is A)
aSb | ab

57. Consider a grammar with the following productions S--> aab | bac | aB,S --> α S |,S --> α b b | ab,Sα --> bdb | b The above grammar is

A) Context free
B) Regular
C) LR (k)
D) Context sensitive

... Answer is D)
Context sensitive

58. Which of the following statement is wrong?

A) Any regular language can be generated by a context-free grammar
B) All non-regular languages can be generated by CFGs
C) Some non-regular languages cannot be generated by any CFG
D) The intersection of a CFL and regular set is a CFL

... Answer is B)
All non-regular languages can be generated by CFGs

59. Which of the following conversion is not possible (algorithmically)?

A) Nondeterministic TM to deterministic TM
B) Regular grammar to context-free grammar
C) Nondeterministic PDA to deterministic PDA
D) Nondeterministic FSA to deterministic FSA

... Answer is C)
Nondeterministic PDA to deterministic PDA

60. The grammars G = ( { s }, { a, b }, p , s) where, p = (s —> 0S1, S —> 0S, S —> S1, S —>a} is a

A) Context-sensitive language
B) Context-free language
C) Regular language
D) Recursively enumerable language

... Answer is C)
Regular language

« Previous Next »