Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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?
5
4
6
3
DFA (Deterministic Finite Automaton) is denoted as a 5 tuple: M = (Q, Σ, δ, q0, F).
Consider the following example of DFA:
Let DFA M = (Q, Σ, δ, q0, F) where:
Q = {q0, q1, q2, q3}
Σ = {0, 1} q0 is the start state
F = {q1, q2} is the set of accept states
δ is the transition function and is denoted for the following table:
| δ | Input: 0 | Input: 1 |
|---|---|---|
| q0 | q0 | q1 |
| q1 | q2 | q2 |
| q2 | q3 | q2 |
| q3 | q0 | q2 |
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
No
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
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)?
No
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?
No
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.
