Computer Science Homework Solutions
Problem
#122400

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)

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.


Solution Summary

The language define 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.

Solution
What is this?
By OTA - Overall OTA Rating
Jonathan Hoch, PhD (IP) - 5/5
Purchase Cost Now
$2.19 CAD (was ~$3.99)
Included in Download
  • Plain text response
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • 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 sym ...
  • Theory of Computation/Computer Science Problem - Consider the following three languages, all subsets of Σ* where Σ={a,b}: (1) L1 = {w l w is a word with odd number of a's} (2) L2 = {w l w is a word that ends with a b} (this que ...
  • Automata and Computability - Let A = (attached) R and S are regular expressions and L(R)  L(S) . Show that A is decidable.
  • Automata and Computability - Let A = (attached) | R is a regular expression describing a language containing at least one string w that has 111 as a substring (i.e., w = x111y for some x and y)}. Show that A is decidable.
  • 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 ...
Browse