Two Dimensional Finite Automation
Not what you're looking for?
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.
Purchase this Solution
Solution Summary
Two Dimensional Finite Automation is examined.
Solution Preview
Please see the attached file.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Javscript Basics
Quiz on basics of javascript programming language.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Basic Networking Questions
This quiz consists of some basic networking questions.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.