TAFL Unit 5 Quiz

A Turing machine is said to accept a language if:

• It halts on all inputs.

• It halts and enters an accepting state for strings in the language.

• It halts for all strings not in the language.

• It processes all strings in finite time.

Which of the following problems is undecidable?

• Checking if a DFA accepts all strings.

• Halting problem for Turing machines.

• Checking if a regular expression defines a non-empty language.

• Checking if a CFG generates a finite language.

The class of languages accepted by a Linear Bounded Automaton (LBA) is:

• Regular Languages.

• Context-Free Languages.

• Context-Sensitive Languages.

• Recursive Languages.

Church's Thesis suggests that:

• Recursive functions cannot be computed by Turing machines.

• All effectively computable functions are computable by a Turing machine.

• Only finite automata can compute functions.

• Turing machines are less powerful than real computers.

Post's Correspondence Problem (PCP) is:

• Always solvable.

• Decidable.

• Undecidable.

• A problem for DFA.

Which language class is both recursively enumerable and recursive?

• Regular languages.

• Recursive languages.

• Context-free languages.

• None.

Which of the following can be computed by a Universal Turing Machine?

• Only numerical functions.

• Only regular languages.

• Any computable function.

• Only context-free languages.

In the basic Turing Machine model, the tape is:

• Finite and circular.

• Infinite and one-directional.

• Infinite and bidirectional.

• Finite but rewritable.

Recursive languages are:

• Accepted by Turing machines that halt on all inputs.

• Non-decidable.

• The same as regular languages.

• Computed by finite automata.

If a language is accepted by a non-deterministic Turing Machine, then:

• It is always regular.

• It is recursive.

• It is recursively enumerable.

• It is context-free.