What is the language accepted by a Deterministic Finite Automaton with NO reachable final states?
If no final state can be reached from the initial state q0, the automaton accepts zero strings, representing the empty language ∅.
In a Two-Way Deterministic Finite Automaton (2DFA), what operations can the read head perform on the input tape?
A 2DFA can move its read head in both directions over a read-only input tape without writing capability.
Are Two-Way Deterministic Finite Automata (2DFA) strictly more powerful in language recognition capability than standard 1DFA?
By Shepherdson's Theorem (1959), any 2DFA can be converted to an equivalent 1DFA, proving identical language recognition power.
In converting a Mealy machine with M states to a Moore machine, why might the resulting Moore machine have MORE states than M?
Moore machine outputs are bound to states; if state q in a Mealy machine is reached via edges outputting '0' and '1', q must split into (q, 0) and (q, 1).
What regular expression represents all binary strings over {0, 1} that do NOT contain the substring '00'?
The expression (1 + 01)* allows any combination of '1's and single '01' units, with an optional trailing '0' (via $\epsilon + 0), guaranteeing no adjacent '00'$.