Home » MCQs

Theory of Computation Multiple-Choice Questions (MCQs)

Theory of computation (TOC) is a branch of Computer Science that deals with the problems that can be solved on a model of computation using an algorithm.

Theory of Computation MCQs: This section contains multiple-choice questions and answers on the various topics of Theory of Computation. Practice these MCQs to test and enhance your skills on Theory of Computation.

List of Theory of Computation MCQs

1. What is a Finite automaton?

1. A Finite automaton is an automaton having an infinite number of states.
2. A Finite automaton is an automaton having a finite number of states

Answer: B) A Finite automaton is an automaton having a finite number of states

Explanation:

A Finite automaton is an automaton having a finite number of states.

Discuss this Question

---

2. An automaton is made up of ____.

1. States
2. Transitions
3. Both

Answer: C) Both

Explanation:

An automaton is made up of states and transitions.

Discuss this Question

---

3. In the theory of automation, how do we represent states?

1. Rectangle
2. Arrow
3. Circles

Answer: C) Circles

Explanation:

States are represented by circles.

Discuss this Question

---

4. In the theory of automation, how do we represent transitions?

1. Triangle
2. Circles
3. Double circles
4. Arrows

Answer: D) Arrows

Explanation:

In the theory of automation, arrows represent transitions.

Discuss this Question

---

5. ____ are entities or single objects that can be any letter, alphabet, or picture.

1. Objects
2. Transitions
3. Symbols
4. Alphabets

Answer: C) Symbols

Explanation:

Symbols are entities or single objects that can be any letter, alphabet, or picture.

Discuss this Question

---

6. What are the alphabets in the theory of computations?

1. Alphabets are a finite set of symbols
2. Alphabets are an infinite set of symbols

Answer: A) Alphabets are a finite set of symbols

Explanation:

Alphabets are a finite set of symbols.

Discuss this Question

---

7. Which of the following is used to denote alphabets?

1. W
2. ∑
3. |W|
4. ~

Answer: B) ∑

Explanation:

Alphabets are a finite set of symbols. It is denoted by ∑.

Discuss this Question

---

8. ____ is a finite collection of symbols from the alphabet.

1. Switch
2. String
3. State
4. Symbols

Answer: B) String

Explanation:

A string is a finite collection of symbols from the alphabet.

Discuss this Question

---

9. The string is denoted by ____.

1. w
2. A
3. G
4. s

Answer: A) w

Explanation:

The string is denoted by w.

Discuss this Question

---

10. A string with zero occurrences of symbols is known as an ____ string.

1. Unfilled string
2. End string
3. Empty string

Answer: C) Empty string

Explanation:

A string with zero occurrences of symbols is known as an empty string.

Discuss this Question

---

11. Empty string is denoted by ____.

1. 0
2. E
3. $
4. ε

Answer: D) ε

Explanation:

Empty string is represented by ε.

Discuss this Question

---

12. Length of a string is represented by ____.

1. Null
2. L
3. |Length|
4. |w|

Answer: D) |w|

Explanation:

The length of a string is defined as the number of symbols in a string w. It's represented by |w|.

Discuss this Question

---

13. Suppose w= 110. So, what would be the length of a string?

1. 2
2. 0
3. 3
4. None

Answer: C) 3

Explanation:

w = 110 Number of String |w| = 3.

Discuss this Question

---

14. How many states do finite automata have?

1. 1
2. 2
3. 3
4. None

Answer: B) 2

Explanation:

Finite automata have two states: Accept and Reject.

Discuss this Question

---

15. A finite automaton is a collection of how many tuples?

1. 5
2. 4
3. 3
4. 2

Answer: A) 5

Explanation:

A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F).

Discuss this Question

---

16. How many types of finite automata are there?

1. 4
2. 3
3. 5
4. 2

Answer: D) 2

Explanation:

There are two types of finite automata:

• DFA(deterministic finite automata)
• NFA(non-deterministic finite automata)

Discuss this Question

---

17. In the ____, the machine only goes to one state for each input character.

1. DFA
2. NFA

Answer: A) DFA

Explanation:

In the DFA, the machine only goes to one state for each input character.

Discuss this Question

---

18. Does DFA accepts null moves?

1. Yes
2. No

Answer: B) No

Explanation:

The null move is not accepted by DFA.

Discuss this Question

---

19. Does NFA accepts null moves?

1. Yes
2. No

Answer: A) Yes

Explanation:

The null move is accepted by NFA.

Discuss this Question

---

20. Which of the following statement is True?

1. Every DFA is NFA, also every NFA is DFA
2. Every DFA is NFA, but NFA is not DFA

Answer: B) Every DFA is NFA, but NFA is not DFA.

Explanation:

Every DFA is NFA, but NFA is not DFA.

Discuss this Question

---

21. In both NFA and DFA, several end states are possible.

1. True
2. False

Answer: A) True

Explanation:

There can be multiple final states in both NFA and DFA.

Discuss this Question

---

22. Which of the following is utilized in Lexical Analysis in Compiler?

1. DFA
2. NFA

Answer: A) DFA

Explanation:

DFA is used in Lexical Analysis in Compiler.

Discuss this Question

---

23. Which of the following indicates accepting or final states?

1. Double circles
2. Triangle
3. Double dash
4. circle

Answer: A) Double circles

Explanation:

Double circles indicate accepting or final states.

Discuss this Question

---

24. A transition diagram or state transition diagram is a ____ graph?

1. Undirected
2. Directed

Answer: B) Directed

Explanation:

A transition diagram or state transition diagram is a directed graph.

Discuss this Question

---

25. For specified input, there can be how many paths from the current state to the next state in DFA?

1. Many
2. None
3. One
4. Zero

Answer: C) One

Explanation:

For specified input, there is only one path from the current state to the next state in DFA.

Discuss this Question

---

26. DFA Transition function can be defined as ____.

1. δ: Q x ∑→Q
2. W: Q x ∑→Q
3. δ: Q x ∑→W
4. δ: Q x ∑→F

Answer: A) δ: Q x ∑→Q

Explanation:

DFA Transition function can be defined as: δ: Q x ∑→Q.

Discuss this Question

---

27. In a ring topology, data flows in a ____ manner.

1. Anti clockwise
2. Clockwise

Answer: B) Clockwise

Explanation:

In a ring topology, data flows in a clockwise manner.

Discuss this Question

---

28. NFA has how many states?

1. 2
2. 3
3. 4
4. 5

Answer: D) 5

Explanation:

NFA also has five states same as DFA.

Discuss this Question

---

29. How do you define a transition function of NFA?

1. δ: Q x ∑ →3Q
2. δ: Q x ∑ →2Q
3. δ: Q x ∑ →4Q
4. δ: Q x ∑ →FQ

Answer: B) δ: Q x ∑ →2Q

Explanation:

The five states of NFA are identical to those of DFA but have distinct transition functions δ: Q x ∑ →2Q.

Discuss this Question

---

30. The language accepted by finite automata can be easily described by simple expressions called ____.

1. Constant expression
2. Frequent expression
3. Regular expression
4. Conventional expression

Answer: C) Regular expression

Explanation:

The language accepted by finite automata can be easily described by simple expressions called Regular Expressions.

Discuss this Question

---

31. Which types of languages are accepted by regular expressions?

1. Regular language
2. Consistent language
3. Kleen language
4. Series language

Answer: A) Regular language

Explanation:

Regular languages are the languages that are accepted by some regular expressions.

Discuss this Question

---

32. If L is a regular language, then its Kleen closure L1* will ____.

1. will not be a regular language
2. will also be a regular language

Answer: B) will also be a regular language.

Explanation:

If L is a regular language, then its Kleen closure L1* will also be a regular language.

Discuss this Question

---

33. What will be the regular expression for the language accepting all the strings which are starting with 1 and ending with 0, over ∑ = {0, 1}?

1. R = 1 (0+1)* 1
2. R = 1 (0+1)+ 0
3. R = 1 (0+1)* 0
4. R = 1 (0+1)+1

Answer: C) R = 1 (0+1)* 0

Explanation:

The initial symbol in a regular expression should be 1, and the last symbol should be 0, so the regular expression will be R = 1 (0+1)* 0.

Discuss this Question

---

34. A ____ machine is a finite state machine in which the current state and current input symbol determine the future state.

1. Moore
2. Mealy

Answer: A) Moore

Explanation:

A Moore machine is a finite-state machine in which the current state and current input symbol determine the future state.

Discuss this Question

---

35. Moore machine is described by how many tuples?

1. 5
2. 4
3. 3
4. 6

Answer: D) 6

Explanation:

Moore machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ) where,

• Q: a finite set of states
• q0: the initial state of the machine
• ∑: a finite set of input symbols
• O: output alphabet
• δ: transition function where Q × ∑ → Q
• λ: output function where Q → O

Discuss this Question

---

36. What is the Mealy machine?

1. A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the present state of the machine
2. A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the next stage of the machine
3. A Mealy machine is a machine in which the output symbol depends upon the next input symbol and the next stage of the machine
4. A Mealy machine is a machine in which the output symbol depends upon the next input symbol and the present state of the machine

Answer: A) A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the present state of the machine.

Explanation:

A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the present state of the machine.

Discuss this Question

---

37. Mealy machine has how many tuples?

1. 5
2. 4
3. 3
4. 6

Answer: D) 6

Explanation:

The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, X') where

• Q: a finite set of states
• q0: the initial state of the machine
• ∑: a finite set of the input alphabet
• O:output alphabet
• δ: transition function where Q × ∑ → Q
• X:is the output transition function which maps Q × ∑ into O

Discuss this Question

---

38. What do you mean by CFG in the theory of computations?

1. Common free grammar
2. Context form grammar
3. Context full grammar
4. Content-free grammar

Answer: D) Content-free grammar

Explanation:

CFG stands for context-free grammar.

Discuss this Question

---

39. CFG has how many tuples?

1. 2
2. 3
3. 4
4. 5

Answer: C) 4

Explanation:

Context-free grammar G can be defined by four tuples:G = (V, T, P, S):

• G is the grammar
• T is the final set of a terminal symbol
• V is the final set of a non-terminal symbol
• P is a set of production rules
• S is the start symbol

Discuss this Question

---

40. In CFG terminal symbols are denoted by ____.

1. Lowercase letter
2. Upper case letter
3. Camel case letter

Answer: A) Lowercase letter

Explanation:

In CFG, the terminal symbols are denoted by lowercase letters.

Discuss this Question

---

41. How do we denote the non-terminal symbol?

1. Lowercase letter
2. Upper case letter
3. Camel case letter

Answer: B) Upper case letter

Explanation:

Non-terminal symbols are denoted by capital letters.

Discuss this Question

---

42. The input is scanned and replaced with the production rule from left to right in the ____ derivation.

1. Right most deviation
2. Left most deviation

Answer: B) Left most deviation

Explanation:

The input is scanned and replaced with the production rule from left to right in the leftmost derivation.

Discuss this Question

---

43. How do we read the input string in the rightmost derivation?

1. From right to left
2. From left to right

Answer: A) From right to left

Explanation:

We read the input string from right to left in the rightmost derivation.

Discuss this Question

---

44. The derivation tree is also known as ____.

1. Comprehend tree
2. Deviated tree
3. Decipher tree
4. Parse tree

Answer: D) Parse tree

Explanation:

The derivation tree is also known as the parse tree.

Discuss this Question

---

45. In a parse tree, the root node always represents a ____ symbol.

1. T (the final set of a terminal symbol)
2. V (the final set of a non-terminal symbol)
3. P (a set of production rules)
4. S (the start symbol)

Answer: D) S (the start symbol).

Explanation:

The root node is always a node that represents a start symbol.

Discuss this Question

---

46. In a parse tree, the leaf node always contains ____.

1. Non-terminal node
2. Terminal node

Answer: B) Terminal node

Explanation:

In a parse tree, the leaf node always has terminal nodes.

Discuss this Question

---

47. A grammar is said to be ambiguous if ____.

1. There exists more than one leftmost derivation
2. More than one rightmost derivation
3. More than one parse tree for the given input string
4. None
5. All of the above

Answer: E) All of the above

Explanation:

A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string.

Discuss this Question

---

48. What do you mean by CNF?

1. Chomsky's normal form
2. Chimpken normal form
3. Campbell's normal form

Answer: A) Chomsky's normal form

Explanation:

CNF stands for Chomsky's normal form.

Discuss this Question

---

49. The extra memory in pushdown automata is known as ____.

1. Heap
2. Array
3. Stack
4. None

Answer: C) Stack

Explanation:

Pushdown automaton is a finite automaton with additional memory known as a stack.

Discuss this Question

---

50. Among PDA and FA which is more powerful?

1. PDA
2. FA

Answer: A) PDA

Explanation:

A PDA (pushdown automata) is more powerful than FA (finite automata).

Discuss this Question

---

51. Which of the following statement is True?

1. Any language which can be acceptable by FA can also be acceptable by PDA
2. Any language which can be acceptable by FA cannot be acceptable by PDA

Answer: A) Any language which can be acceptable by FA can also be acceptable by PDA.

Explanation:

Any language which can be acceptable by FA can also be acceptable by PDA.

Discuss this Question

---

52. The CFG that accepts deterministic PDAs also allows non-deterministic PDAs?

1. False
2. True

Answer: B) True

Explanation:

The CFG that accepts deterministic PDAs also allows non-deterministic PDAs.

Discuss this Question

---

53. Which is more powerful NPDA (non-deterministic PDA) and DPDA (deterministic PDA)?

1. NPDA
2. DPDA

Answer: A) NPDA

Explanation:

Some CFGs can only be accepted by NPDA and not by DPDA. As a result, NPDA is more potent than DPDA.

Discuss this Question

---

54. According to Chomsky's hierarchy which of the following represents unrestricted grammar?

1. TYPE 3
2. TYPE 2
3. TYPE 1
4. TYPE 0

Answer: D) TYPE 0

Explanation:

According to Chomsky's hierarchy TYPE 0 represents unrestricted grammar.

Discuss this Question

---

55. According to Chomsky's hierarchy which of the following represents context-free grammar?

1. TYPE 3
2. TYPE 2
3. TYPE 1
4. TYPE 0

Answer: B) TYPE 2

Explanation:

According to Chomsky's hierarchy TYPE 2 represents context-free grammar.

Discuss this Question

---

56. According to Chomsky's hierarchy which of the following represents Regular grammar?

1. TYPE 3
2. TYPE 2
3. TYPE 1
4. TYPE 0

Answer: A) TYPE 3

Explanation:

According to Chomsky's hierarchy TYPE 3 represents regular grammar.

Discuss this Question

---

57. According to Chomsky's hierarchy which of the following represents context-sensitive grammar?

1. TYPE 3
2. TYPE 2
3. TYPE 1
4. TYPE 0

Answer: C) TYPE 1

Explanation:

According to Chomsky's hierarchy TYPE 1 represents context-sensitive grammar.

Discuss this Question

---

58. Which of the following statement is True?

1. Every type 2 language is also a type 1 and a type 3
2. Every type 2 language is also a type 3 and a type 0
3. Every type 2 language is also a type 1 and a type 0

Answer: C) Every type 2 language is also a type 1 and a type 0

Explanation:

Every type 2 language is also a type 1 and a type 0.

Discuss this Question

---

59. Which of the following automatons is the most powerful?

1. Finite Automaton
2. Pushdown Automaton
3. Turing Machine
4. None of the above

Answer: C) Turing Machine

Explanation:

The turing machine is the most powerful.

Discuss this Question

---

60. Context-free grammar can be recognized by ____.

1. Finite Automaton
2. Pushdown Automaton
3. Turing Machine

Answer: B) Pushdown Automaton

Explanation:

Context-free grammar can be recognized by the pushdown automaton.

Discuss this Question

---