1
A TM halts if it:
Correct Answer
Both A and B
☑ MCQ PRACTICE
Formal Languages and Automata Theory Unit 5
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Formal Languages and Automata Theory - Unit-5
2
The Halting Problem for TMs is:
Correct Answer
Undecidable
3
A Universal Turing Machine can:
Correct Answer
Simulate any other TM
4
A TM with multiple tapes is:
Correct Answer
Equivalent to a single-tape TM
5
The class of languages decidable by TMs is called:
Correct Answer
Recursive
6
A non-deterministic TM is:
Correct Answer
Equivalent to a deterministic TM
7
A multi-tape Turing Machine is:
Correct Answer
Equivalent to a single-tape TM
8
A non-deterministic Turing Machine is:
Correct Answer
Equivalent to a deterministic TM
9
The Halting Problem concerns determining whether a Turing Machine will:
Correct Answer
Halt on a given input
10
A Universal Turing Machine can:
Correct Answer
Simulate any other Turing Machine
11
A Turing Machine with a read-only input tape and a working tape is called:
Correct Answer
Linear Bounded Automaton
12
A language is recursively enumerable (RE) if:
Correct Answer
Both a and b
13
The Halting Problem is:
Correct Answer
Undecidable but RE
14
An example of a language that is not RE is:
Correct Answer
The set of all TMs that do not halt on any input
15
Post's Correspondence Problem (PCP) is:
Correct Answer
Undecidable
16
A recursive language is one that is:
Correct Answer
Accepted by a TM that always halts
17
Rice's Theorem states that:
Correct Answer
All non-trivial properties of RE languages are undecidable
18
The Membership Problem for TMs is:
Correct Answer
Undecidable
19
A counter machine is a TM with:
Correct Answer
Only integer counters instead of a tape
20
The Modified Post Correspondence Problem is:
Correct Answer
Undecidable like PCP
21
The problem of determining if two TMs accept the same language is:
Correct Answer
Undecidable
22
Recursive languages are closed under:
Correct Answer
All of the above
23
If L and its complement are both RE, then L is:
Correct Answer
Recursive
24
The complement of a recursive language is:
Correct Answer
Recursive
25
The set of all TMs that halt on all inputs is:
Correct Answer
Not RE
26
A property of recursive languages is that they can be decided by a TM that:
Correct Answer
Always halts
27
The problem of determining if a TM accepts a regular language is:
Correct Answer
Undecidable
28
The Blank Tape Halting Problem is:
Correct Answer
Undecidable
29
The problem of determining if a TM has at least 5 states is:
Correct Answer
Decidable
30
Counter machines with two counters are as powerful as:
Correct Answer
Turing Machines
31
The problem of determining if a TM ever writes a specific symbol on its tape is:
Correct Answer
Undecidable