Interview Questions on Theory of Computation (MCQ)

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have present Interview Questions on Theory of Computation (MCQ). You must attempt these questions. All answers have been provided which will help you get prepared in Theory of Computation.

Let us get started with Interview Questions on Theory of Computation (MCQ).

1. What is the definition of Algorithm according to Theory of Computation?

Turing Machine

Multi-tape Turing Machine

Automaton

Regular Expression

In Theory of Computation, Algorithm is defined as a series of steps which can be implemented / followed in a Turing Machine. Other models like Automaton can weaker than Turing Machine. There are other definitions of Algorithms but it has been proved that all definitions are equivalent to Turing Machine.

2. Halting Problem is classified as which problem?

Undecidable

NP Hard

NP complete

Decidable

Halting Problem is an undecidable problem and hence, cannot be solved using a Turing Machine. It is a problem that no Computation machine can solve and this has been proved in Theory of Computation.

3. Chomsky Hierarchy is an useful hierarchy of different class of languages in Theory of Computation. When was Chomsky Hierarchy first discovered?

1956

1959

1991

1964

Chomsky Hierarchy was first formed in 1956 by Noam Chomsky. It was presented in a paper titled "On Certain Formal Properties of Grammars, Information and Control" in 1959. To learn more about Chomsky Hierarchy, go through this article

4. Which computation model is used to decide if a string in a Context Sensitive Language?

Linear Bounded Automaton

Turing Machine

Pushdown Automaton

Finite State Automaton

Linear Bounded Automaton is used to decide if a string in a Context Sensitive Language.

5. Which computation model is used to decide if a string in a Context Free Language?

Pushdown Automaton

Linear Bounded Automaton

Turing Machine

Finite State Automaton

Pushdown Automaton is used to decide if a string in a Context Free Language.

6. Which computation model is used to decide if a string in a Regular Language?

Finite State Automaton

Pushdown Automaton

Linear Bounded Automaton

Turing Machine

Finite State Automaton is used to decide if a string in a Regular Language.

7. What is the Language accepted by a Turing Machine known as?

Recursively Enumerable

Context Sensitive

Context Free

Regular

Recursively Enumerable Language is the strongest class of Language in Theory of Computation and it can be accepted only using a Turing Machine.

8. In Theory of Computation, it is proved that Quantum Computer is same as Modern Electrical Computers. Which model is stronger than current computers?

Super Recursive Algorithm

Recursive Algorithm

Molecular Computer

Nuclear Computer

Theory of Computer presents Super Recursive Algorithm which is more powerful than the current models like Quantum Computers and Traditional Computers. Therefore, all other models are same which means it can solve the same set of problems and not any extra problem.

This is the Chomsky Hierarchy in Theory of Computation:

Type	Language	Automata Machine	Power
Type 0	Recursively Enumerable	Turing Machine	Strongest
Type 1	Context Sensitive	Linear Bounded Automaton	Stronger
Type 2	Context Free	Pushdown Automaton	Strong
Type 3	Regular	Finite State Automaton	Weak

9. What is the name of the Language that is added in Extended Chomsky Hierarchy in between Type 0 and Type 1?

Recursive Language

Recognizable Language

Deterministic Context Free Language

PSPACE complete Language

Recursive Language is the language that has been added in between Type 0 and Type 1 in Chomsky Hierarchy to form the Extended Chomsky Hierarchy. To learn move about Extended Chomsky Hierarchy, go through this article.

10. Which is the weakest language among the following in Theory of Computation?

Presburger Arithmetic Language

Context Free Language

Regular Language

NP complete Language

Presburger Arithmetic Language is the weakest language among the listed Languages. To understand the categorization of different languages in Theory of Computation, go through this article.

11. Deterministic Finite Automaton (DFA) is defined as a N-tuple. What is N?

DFA (Deterministic Finite Automaton) is denoted as a 5 tuple: M = (Q, Σ, δ, q₀, F).

Consider the following example of DFA:

Let DFA M = (Q, Σ, δ, q₀, F) where:

Q = {q₀, q₁, q₂, q₃}
Σ = {0, 1} q₀ is the start state
F = {q₁, q₂} is the set of accept states
δ is the transition function and is denoted for the following table:

δ	Input: 0	Input: 1
q₀	q₀	q₁
q₁	q₂	q₂
q₂	q₃	q₂
q₃	q₀	q₂

12. What is the above table for the transition table known as?

State Transition Table

State Table

State Diagram

Transition Table

The table depicting the different transition in a DFA is known as State Transition Table.

13. Is Deterministic Finite Automata (DFA) is same as Nondeterministic Finite Automata (NFA)?

Yes

Yes, only for linear random functions

Depends on Language

Deterministic Finite Automata (DFA) is equivalent to Nondeterministic Finite Automata (NFA). For proving that for every NFA, there is an equivalent DFA in 1959, the Turing Award was given to Rabin and Scott.

14. Which concept in Theory of Computation resulted in the development of the popular Knuth Morris Pratt (KMP) Algorithm in 1976?

Deterministic Finite Automata

Non-deterministic Finite Automata

Turing Machine

Finite Automaton

DFA has resulted in the discovery of Knuth Morris Pratt Algorithm in 1976 which is a very popular string searching algorithm today.

Consider the following definition and statements in Theory of Computation:

We define subsequence as:

SUBSEQ(L) = {x : there exists y ∈ L such that x is a subsequence of y}.

In simple terms, SUBSEQ(L) is a language that consist of subsequence of all strings in L.

A popular Theorem states that: For any finite alphabet Σ and for a given language L which is a proper subset of Σ*, then the language SUBSEQ(L) is a regular language.

15. Which theorem states the above statement in Theory of Computation?

Higman's Theorem

Rice's Theorem

Pumping Lemma

Church Turing Theorem

Highman's Theorem states that: For any finite alphabet Σ and for a given language L which is a proper subset of Σ*, then the language SUBSEQ(L) is a regular language.
Higman's Theorem was found in 1952. To learn more, go through this article

16. Which language in Theory of Computation is undecidable?

A_Turing_Machine

A_DFA

A_NFA

A_Pushdown_Automaton

A_Turing_Machine is an Undecidable Language in Theory of Computation. To learn about Decidability in Theory of Computation, go through this article.

17. Which Grammar is strong enough for the language a^N b^N c^N ?

Context Sensitive Grammar

Context Free Grammar

Regular Grammer

Deterministic Context Free Grammar

Context Sensitive Grammar is the Grammer that can accept strings of the language a^N b^N c^N. Other languages are weak for this as 3 counters need to be maintained. To learn how to use CSG for this, go through this article.

18. For a given language L, what is the operation that is denoted as L*?

Kleene closure

Positive Closure

Exponentiation

Multiplication Closure

Kleene closure is denoted as L*. L+ means Positive closure.

19. Which theorem in Theory of Computation is used to check the equivalence of two regular expressions?

Arden's Theorem

Rice's Theorem

Kadane's Theorem

Higman's Theorem

Arden’s Theorem in Theory of Computation is used to check the equivalence of two regular expressions.

20. Which one is used to check if a given Language L is a Regular Language or not?

Pumping Lemma

Rice's Theorem

Kadane's Theorem

Regular Lemma

Pumping Lemma for Regular Languages is used to check if a given Language L is a Regular Language or not.

21. In Theory of Computation, a string is a list of terminal symbols. What is sentinal form consist of?

Variables + Terminal symbols

Terminal symbols

Variables

Recursive variables

Sentinal is a string of variables and terminal symbols. It appears as an intermediate form in a derivation.

22. Programming Languages are defined by Backus Naur Form (BNF). What does the BNF notation fall under?

Context Free Grammar

Context Sensitive Grammar

Regular Grammar

Deterministic Grammar

Backus Naur Form (BNF) is a notation in Context Free Grammar with small changes in format.

23. What is the configuration of a PDA at a given instant known as?

Instantaneous description

Current configuration

Current state

Accept state

Instantaneous description (ID) is the configuration of a PDA at a given instant.

24. Is Deterministic Pushdown Automata (DPDA) is same as Nondeterministic Pushdown Automata (NPDA)?

Yes

Yes, only for linear random functions

Depends on Language

Unlike Finite Automaton (FA), Deterministic Pushdown Automata (DPDA) is not same as Nondeterministic Pushdown Automata (NPDA).

One of the most important results in Theory of Computation states:

"A computation process that can be represented by an algorithm can be converted to a Turing Machine."

25. What is the above statement known as?

Church Turing Thesis

Extended Chomsky Hierarchy

Dickson's Theorem

Turing Lemma

To learn more about Church Turing Thesis, go through this article.

26. Is Church Turing Thesis universally true?

Yes

Depends on Computation model

Only on large scale

Church Turing Thesis is not universally true. The limitation of Church Turing Thesis is known as Super Recursive Algorithm but these have not been realized in practical life yet and remains in theory. Super Recursive Algorithms are more powerful than Quantum Computers.

With this article at OpenGenus, you must have a good practice of Interview Questions on Theory of Computation (MCQ). Best of luck with your examination or Coding Interview.