Tutorials
PPTs
Lecture Notes
Objective Questions
Lab ProgramsObjective Type Questions & Answers
Formal Languages and Automata Theory (FLAT) MCQs - Unit-5
1. A TM halts if it:
A . Rejects the input
B . Accepts the input
C . Enters a loop
D . Both A and B
2. The Halting Problem for TMs is:
A . Decidable
B . Undecidable
C . NP-complete
D . Context-free
3. A Universal Turing Machine can:
A . Simulate any other TM
B . Only recognize regular languages
C . Solve the Halting Problem
D . Never halt
4. A TM with multiple tapes is:
A . Less powerful than a single-tape TM
B . Equivalent to a single-tape TM
C . More powerful than a single-tape TM
D . Unable to recognize CFLs
5. The class of languages decidable by TMs is called:
A . P
B . NP
C . Recursive
D . RE
6. A non-deterministic TM is:
A . Weaker than a deterministic TM
B . Equivalent to a deterministic TM
C . Unable to recognize RE languages
D . More powerful than a deterministic TM
7. A multi-tape Turing Machine is:
A . Less powerful than a single-tape TM
B . More powerful than a single-tape TM
C . Equivalent to a single-tape TM
D . Unable to recognize regular languages
8. A non-deterministic Turing Machine is:
A . Weaker than a deterministic TM
B . More powerful than a deterministic TM
C . Equivalent to a deterministic TM
D . Unable to solve NP problems
9. The Halting Problem concerns determining whether a Turing Machine will:
A . Accept a given input
B . Reject a given input
C . Halt on a given input
D . Enter an infinite loop
10. A Universal Turing Machine can:
A . Only solve the Halting Problem
B . Simulate any other Turing Machine
C . Recognize only regular languages
D . Never halt
11. A Turing Machine with a read-only input tape and a working tape is called:
A . Multi-tape TM
B . Linear Bounded Automaton
C . Counter Machine
D . Quantum TM
12. A language is recursively enumerable (RE) if:
A . There exists a TM that halts and accepts all strings in the language
B . There exists a TM that may loop infinitely on strings not in the language
C . Both a and b
D . There exists a TM that always halts
13. The Halting Problem is:
A . Decidable
B . Undecidable but RE
C . Not RE
D . Regular
14. An example of a language that is not RE is:
A . The set of all TMs that halt on empty input
B . The set of all TMs that do not halt on any input
C . The set of all TMs that accept regular languages
D . The set of all valid C programs
15. Post`s Correspondence Problem (PCP) is:
A . Decidable
B . Undecidable
C . NP-complete
D . Regular
16. A recursive language is one that is:
A . Accepted by a TM that always halts
B . Accepted by a TM that may loop
C . Not accepted by any TM
D . Accepted only by non-deterministic TMs
17. Rice`s Theorem states that:
A . All non-trivial properties of RE languages are undecidable
B . Some problems about TMs are decidable
C . The Halting Problem is decidable
D . PCP is decidable
18. The Membership Problem for TMs is:
A . Decidable
B . Undecidable
C . Decidable only for finite languages
D . Decidable only for regular languages
19. A counter machine is a TM with:
A . Multiple tapes
B . A stack instead of a tape
C . Only integer counters instead of a tape
D . No halting state
20. The Modified Post Correspondence Problem is:
A . Easier than PCP
B . Undecidable like PCP
C . Decidable
D . A regular language problem
21. The problem of determining if two TMs accept the same language is:
A . Decidable
B . Undecidable
C . NP-complete
D . Context-free
22. Recursive languages are closed under:
A . Union
B . Intersection
C . Complement
D . All of the above
23. If L and its complement are both RE, then L is:
A . Recursive
B . Not recursive
C . Regular
D . Context-free
24. The complement of a recursive language is:
A . Recursive
B . RE but not recursive
C . Not RE
D . Undecidable
25. The set of all TMs that halt on all inputs is:
A . Recursive
B . RE but not recursive
C . Not RE
D . Finite
26. A property of recursive languages is that they can be decided by a TM that:
A . May loop on some inputs
B . Always halts
C . Only accepts regular languages
D . Uses non-determinism
27. The problem of determining if a TM accepts a regular language is:
A . Decidable
B . Undecidable
C . NP-complete
D . P-complete
28. The Blank Tape Halting Problem is:
A . Decidable
B . Undecidable
C . Equivalent to PCP
D . A regular language
29. The problem of determining if a TM has at least 5 states is:
A . Decidable
B . Undecidable
C . Semi-decidable
D . Context-sensitive
30. Counter machines with two counters are as powerful as:
A . Finite automata
B . Pushdown automata
C . Turing Machines
D . Linear Bounded Automata
31. The problem of determining if a TM ever writes a specific symbol on its tape is:
A . Decidable
B . Undecidable
C . NP-complete
D . P-complete
Relevant Materials :
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]
Similar Materials :
☞ R - Programming MCQs - Unit-1 - [ R-Programming ]
☞ R - Programming MCQs - Unit-2 - [ R-Programming ]
☞ R - Programming MCQs - Unit-3 - [ R-Programming ]
☞ R - Programming MCQs - Unit-4 - [ R-Programming ]
☞ R - Programming MCQs - Unit-5 - [ R-Programming ]
☞ Artificial Intelligence (AI) MCQs - Unit-1 - [ Artificial Intelligence ]
☞ Artificial Intelligence (AI) MCQs - Unit-2 - [ Artificial Intelligence ]
☞ Artificial Intelligence (AI) MCQs - Unit-3 - [ Artificial Intelligence ]
☞ Artificial Intelligence (AI) MCQs - Unit-4 - [ Artificial Intelligence ]
☞ Artificial Intelligence (AI) MCQs - Unit-5 - [ Artificial Intelligence ]
☞ PPS MCQs - Unit-1 - [ PPS ]
☞ PPS MCQs - Unit-2 - [ PPS ]
☞ PPS MCQs - Unit-3 - [ PPS ]
☞ PPS MCQs - Unit-4 - [ PPS ]
☞ PPS MCQs - Unit-5 - [ PPS ]
☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]
☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]
☞ Software Engineering MCQs - Unit-1 - [ SE ]
☞ Software Engineering MCQs - Unit-2 - [ SE ]
☞ Software Engineering MCQs - Unit-3 - [ SE ]
☞ Software Engineering MCQs - Unit-4 - [ SE ]
☞ Software Engineering MCQs - Unit-5 - [ SE ]
☞ Data Mining MCQs - Unit-1 - [ DM ]
☞ Data Mining MCQs - Unit-2 - [ DM ]
☞ Data Mining MCQs - Unit-3 - [ DM ]
☞ Data Mining MCQs - Unit-4 - [ DM ]
☞ Data Mining MCQs - Unit-5 - [ DM ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]
☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]
☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]