Explore topic-wise MCQs in Automata Theory.

This section includes 6 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.

With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.

A. true
B. false
Answer» B. false
Discussion
2.

Which of the following is true for The Halting problem?

A. It is recursively enumerable
B. It is undecidable
C. It is recursively enumerable and undecidable
D. None of the mentioned
Answer» D. None of the mentioned
Discussion
3.

Statement: If L id R.E., Lc needs to be R.E. Is it correct?

A. Yes
B. No
C. Maybe
D. Cannot predict
Answer» C. Maybe
Discussion
4.

7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}

A. A concrete undecidable problem
B. A is recognizable but not decidable
C. -A is not recognizable
D. All of the mentioned
Answer» E.
Discussion
5.

Which of the following are decidable problems?

A. Can a particular line of code in a program ever be executed?
B. Do two given CFG s generate the same language
C. Is a given CFG ambiguous?
D. None of the mentioned
Answer» E.
Discussion
6.

Which of the following technique is used to find whether a natural language isn t recursive enumerable?

A. Diagonalization
B. Recursive Induction
C. All of the mentioned
D. None of the mentioned
Answer» B. Recursive Induction
Discussion