Explore topic-wise MCQs in Automata Theory.

This section includes 5 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.

1.

State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?

A. nThe given problem is P-complete.
B. true
C. false
Answer» B. true
Discussion
2.

Which of the following is a P-complete type of problem?

A. Circuit Value problem
B. Linear programming
C. Context free grammar membership
D. All of the mentioned
Answer» E.
Discussion
3.

A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.

A. 1
B. 2
C. 3
D. all of the mentioned
Answer» E.
Discussion
4.

The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.

A. Push Down automata
B. DFA
C. NDFA
D. Deterministic Turing machine
Answer» E.
Discussion
5.

If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:

A. non-polynomial time
B. polynomial time
C. infinite time
D. none of the mentioned
Answer» C. infinite time
Discussion