Computational Automata Theory: True/False Assessment of Turing Machines, Finite Automata, and Decidability
Overview
This document is a true/false assessment examining foundational concepts in computational theory, including Turing machines, finite automata, regular languages, and the halting problem. The questions test understanding of automata simulation, language recognition, recursively enumerable sets, and formal language properties.
What this coursework covers
- Turing machine modifications and the halting problem
- Finite automata equivalence and nondeterminism
- Regular sets, homomorphisms, and language recognition
- Decidability and recursive/recursively enumerable languages
- Deterministic and nondeterministic finite automaton relationships
Preview
A universal Turing machine can be modified to tell whether or not a particular Turing machine will halt if nothing is written on its tape.
True
False
True or false: a Turing machine with a two-way infinite tape can be simulated by the standard Turing machine first defined in the text.
True
False
True or false: the use of e-transitions expands the collection of regular sets, that is, there are sets that are recognized by a finite automaton with such transitions that are not recognized by ordinary finite automata.
True
False
True or false: every regular set of words (over any alphabet) is the range of a homomorphism that has domain {a,b}*
True
False
True or false: every DFA can be simulated by a DFA with a transition function that forbids transitions out of final states.
True
False
True or false: A language accepted by a nondeterministic finite automaton is also accepted by some deterministic finite automaton.
True
False
True or false: a finite state machine can occupy one of finitely many states; therefore the language it recognizes is finite.
True
False
True or False: The halting problem is recursively enumerable.
True
False
True or false: the compliment of the halting problem is recursively enumerable.
True
False
True or False: Every DFA can be simulated by a Turing machine.
True
False
Which string of parentheses does the above graph encode, in the sense of lecture 20 from the text?
Answer is 2
True or false: the halting problem is recursive.