Problem 24
Define two dimensional finite automaton (2DIM-DFA) is defined as
follows. The input is an m X n rectangle, for any m, n ( 2. The
squares along the boundary of the rectangle contain the symbol # and the
internal squares contain symbols over the input alphabet (. The
transition function is a mapping Q x ( ( Q x {L,R,U,D} to indicate the
next state and the new head position (Left, Right, Up, down). The
machine accepts when it enters one of the designated accept states. It
rejects if it tries to move off the input rectangle or if it never
halts. Two such machines are equivalent if they accept the same
rectangles. Consider the problem of testing whether two of these
machines are equivalent. Formulate this problem as a language, and show
that it is undecidable.
Computer Science Homework Solutions
#120804
Two Dimensional Finite Automaton
1. Define two dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an m X n rectangle, for any m, n 2. The squares along the boundary of the rectangle contain the symbol # and the internal squares contain symbols over the input alphabet . The transition function is a mapping Q x Q x {L,R,U,D} to indicate the next state and the new head position (Left, Right, Up, down). The machine accepts when it enters one of the designated accept states. It rejects if it tries to move off the input rectangle or if it never halts. Two such machines are equivalent if they accept the same rectangles. Consider the problem of testing whether two of these machines are equivalent. Formulate this problem as a language, and show that it is undecidable.
See attached file for full problem description.
What is this?
By OTA - Overall OTA Rating
Jonathan Hoch, PhD (IP) - 5/5
Purchase Cost Now
$2.19 CAD (was ~$79.80)
Included in Download
- Plain text response
- Attached file(s):
- Brain.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Automata and Computability - Show that the PCP is undecidable over a binary alphabet, that is, over the alphabet = {0,1}.
- 2DIM-DFA is undecidable - The language define by the equality of two 2DIM-DFA machines on all inputs is undecidable. The full definition of 2DIM-DFA can be found in Sipser's "Introduction to the Theory of Computation" (5.17) ...
- Solutions to array - Solutions to eight-member one-dimensional array. See attached file for full problem description.
- Automata and Computability - Consider the problem of testing whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show ...
- Automata - Let be a 3cnf-formula. An assignment to the variables of is one where each clause contains two literals with unequal truth values. In other words an -assignment s ...
