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?

## 2. Halting Problem is classified as which problem?

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

## 4. Which computation model 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?

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

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

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

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?

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

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

_{0}, F).

Consider the following example of DFA:

Let DFA M = (Q, Î£, Î´, q_{0}, F) where:

Q = {q_{0}, q_{1}, q_{2}, q_{3}}

Î£ = {0, 1} q_{0} is the start state

F = {q_{1}, q_{2}} is the set of accept states

Î´ is the transition function and is denoted for the following table:

Î´ | Input: 0 | Input: 1 |
---|---|---|

q_{0} |
q_{0} |
q_{1} |

q_{1} |
q_{2} |
q_{2} |

q_{2} |
q_{3} |
q_{2} |

q_{3} |
q_{0} |
q_{2} |

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

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

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

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 was found in 1952. To learn more, go through this article

## 16. Which language in Theory of Computation is undecidable?

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

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

## 19. Which 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?

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

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

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

## 24. Is Deterministic Pushdown Automata (DPDA) is 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?

## 26. Is Church Turing Thesis universally true?

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.