Explore BrainMass
Share

2DIM-DFA is undecidable

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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)

I show a reduction to the decidability of a problem which is known to be undecidable and hence prove the undecidability of the original language.

© BrainMass Inc. brainmass.com October 24, 2018, 9:17 pm ad1c9bdddf
https://brainmass.com/computer-science/programming-languages/122400

Solution Preview

We define the language
EQ-2DIM-DFA = {<M1,M2> , M1,M2 are 2DIM-DFA | L(M1)=L(M2)}

Recall that ELBA = {<M> | M is an LBA and L(M) is empty} is un-decidable.
We will reduce ELBA to EQ-2DIM-DFA by showing that if EQ-2DIM-DFA is decidable than so is ELBA.
We first show how to ...

Solution Summary

The language defined by the equality of two 2DIM-DFA machines on all inputs is undeciable. The full definition of 2DIM-DFA can be found in Sipser's "Introduction to the Theory of Computation" (5.17)

I show a reduction to the decidability of a problem which is known to be undecidable and hence prove the undecidability of the original language.

$2.19
See Also This Related BrainMass Solution

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 &#61619; 2. The squares along the boundary of the rectangle contain the symbol # and the internal squares contain symbols over the input alphabet &#61669;. The transition function is a mapping Q x &#61669; &#61614; 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.

View Full Posting Details