# 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?**

- A Finite automaton is an automaton having an infinite number of states.
- 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.

**2. An automaton is made up of ____.**

- States
- Transitions
- Both

**Answer:** C) Both

**Explanation:**

An automaton is made up of states and transitions.

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

- Rectangle
- Arrow
- Circles

**Answer:** C) Circles

**Explanation:**

States are represented by circles.

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

- Triangle
- Circles
- Double circles
- Arrows

**Answer:** D) Arrows

**Explanation:**

In the theory of automation, arrows represent transitions.

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

- Objects
- Transitions
- Symbols
- Alphabets

**Answer:** C) Symbols

**Explanation:**

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

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

- Alphabets are a finite set of symbols
- Alphabets are an infinite set of symbols

**Answer:** A) Alphabets are a finite set of symbols

**Explanation:**

Alphabets are a finite set of symbols.

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

- W
- ∑
- |W|
- ~

**Answer:** B) ∑

**Explanation:**

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

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

- Switch
- String
- State
- Symbols

**Answer:** B) String

**Explanation:**

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

**9. The string is denoted by ____.**

- w
- A
- G
- s

**Answer:** A) w

**Explanation:**

The string is denoted by w.

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

- Unfilled string
- End string
- Empty string

**Answer:** C) Empty string

**Explanation:**

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

**11. Empty string is denoted by ____.**

- 0
- E
- $
- ε

**Answer:** D) ε

**Explanation:**

Empty string is represented by ε.

**12. Length of a string is represented by ____.**

- Null
- L
- |Length|
- |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|.

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

- 2
- 0
- 3
- None

**Answer:** C) 3

**Explanation:**

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

**14. How many states do finite automata have?**

- 1
- 2
- 3
- None

**Answer:** B) 2

**Explanation:**

Finite automata have two states: Accept and Reject.

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

- 5
- 4
- 3
- 2

**Answer:** A) 5

**Explanation:**

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

**16. How many types of finite automata are there?**

- 4
- 3
- 5
- 2

**Answer:** D) 2

**Explanation:**

There are two types of finite automata:

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

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

- DFA
- NFA

**Answer:** A) DFA

**Explanation:**

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

**18. Does DFA accepts null moves?**

- Yes
- No

**Answer:** B) No

**Explanation:**

The null move is not accepted by DFA.

**19. Does NFA accepts null moves?**

- Yes
- No

**Answer:** A) Yes

**Explanation:**

The null move is accepted by NFA.

**20. Which of the following statement is True?**

- Every DFA is NFA, also every NFA is DFA
- 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.

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

- True
- False

**Answer:** A) True

**Explanation:**

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

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

- DFA
- NFA

**Answer:** A) DFA

**Explanation:**

DFA is used in Lexical Analysis in Compiler.

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

- Double circles
- Triangle
- Double dash
- circle

**Answer:** A) Double circles

**Explanation:**

Double circles indicate accepting or final states.

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

- Undirected
- Directed

**Answer:** B) Directed

**Explanation:**

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

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

- Many
- None
- One
- Zero

**Answer:** C) One

**Explanation:**

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

**26. DFA Transition function can be defined as ____.**

- δ: Q x ∑→Q
- W: Q x ∑→Q
- δ: Q x ∑→W
- δ: Q x ∑→F

**Answer:** A) δ: Q x ∑→Q

**Explanation:**

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

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

- Anti clockwise
- Clockwise

**Answer:** B) Clockwise

**Explanation:**

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

**28. NFA has how many states?**

- 2
- 3
- 4
- 5

**Answer:** D) 5

**Explanation:**

NFA also has five states same as DFA.

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

- δ: Q x ∑ →3Q
- δ: Q x ∑ →2Q
- δ: Q x ∑ →4Q
- δ: 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.

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

- Constant expression
- Frequent expression
- Regular expression
- Conventional expression

**Answer:** C) Regular expression

**Explanation:**

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

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

- Regular language
- Consistent language
- Kleen language
- Series language

**Answer:** A) Regular language

**Explanation:**

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

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

- will not be a regular language
- 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.

**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}?**

- R = 1 (0+1)* 1
- R = 1 (0+1)+ 0
- R = 1 (0+1)* 0
- 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.

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

- Moore
- 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.

**35. Moore machine is described by how many tuples?**

- 5
- 4
- 3
- 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

**36. What is the Mealy machine?**

- A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the present state of the machine
- A Mealy machine is a machine in which the output symbol depends upon the present input symbol and the next stage of the machine
- A Mealy machine is a machine in which the output symbol depends upon the next input symbol and the next stage of the machine
- 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.

**37. Mealy machine has how many tuples?**

- 5
- 4
- 3
- 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

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

- Common free grammar
- Context form grammar
- Context full grammar
- Content-free grammar

**Answer:** D) Content-free grammar

**Explanation:**

CFG stands for context-free grammar.

**39. CFG has how many tuples?**

- 2
- 3
- 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

**40. In CFG terminal symbols are denoted by ____.**

- Lowercase letter
- Upper case letter
- Camel case letter

**Answer:** A) Lowercase letter

**Explanation:**

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

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

- Lowercase letter
- Upper case letter
- Camel case letter

**Answer:** B) Upper case letter

**Explanation:**

Non-terminal symbols are denoted by capital letters.

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

- Right most deviation
- 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.

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

- From right to left
- From left to right

**Answer:** A) From right to left

**Explanation:**

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

**44. The derivation tree is also known as ____.**

- Comprehend tree
- Deviated tree
- Decipher tree
- Parse tree

**Answer:** D) Parse tree

**Explanation:**

The derivation tree is also known as the parse tree.

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

- T (the final set of a terminal symbol)
- V (the final set of a non-terminal symbol)
- P (a set of production rules)
- S (the start symbol)

**Answer:** D) S (the start symbol).

**Explanation:**

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

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

- Non-terminal node
- Terminal node

**Answer:** B) Terminal node

**Explanation:**

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

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

- There exists more than one leftmost derivation
- More than one rightmost derivation
- More than one parse tree for the given input string
- None
- 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.

**48. What do you mean by CNF?**

- Chomsky's normal form
- Chimpken normal form
- Campbell's normal form

**Answer:** A) Chomsky's normal form

**Explanation:**

CNF stands for Chomsky's normal form.

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

- Heap
- Array
- Stack
- None

**Answer:** C) Stack

**Explanation:**

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

**50. Among PDA and FA which is more powerful?**

- PDA
- FA

**Answer:** A) PDA

**Explanation:**

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

**51. Which of the following statement is True?**

- Any language which can be acceptable by FA can also be acceptable by PDA
- 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.

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

- False
- True

**Answer:** B) True

**Explanation:**

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

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

- NPDA
- 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.

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

- TYPE 3
- TYPE 2
- TYPE 1
- TYPE 0

**Answer:** D) TYPE 0

**Explanation:**

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

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

- TYPE 3
- TYPE 2
- TYPE 1
- TYPE 0

**Answer:** B) TYPE 2

**Explanation:**

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

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

- TYPE 3
- TYPE 2
- TYPE 1
- TYPE 0

**Answer:** A) TYPE 3

**Explanation:**

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

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

- TYPE 3
- TYPE 2
- TYPE 1
- TYPE 0

**Answer:** C) TYPE 1

**Explanation:**

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

**58. Which of the following statement is True?**

- Every type 2 language is also a type 1 and a type 3
- Every type 2 language is also a type 3 and a type 0
- 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.

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

- Finite Automaton
- Pushdown Automaton
- Turing Machine
- None of the above

**Answer:** C) Turing Machine

**Explanation:**

The turing machine is the most powerful.

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

- Finite Automaton
- Pushdown Automaton
- Turing Machine

**Answer:** B) Pushdown Automaton

**Explanation:**

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

Comments and Discussions!