Finding whether two machines are equivalent

Assignment Help Basic Computer Science

Reference no: EM1369872

A two-dimensionalfinite 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 E. The transition function is a mapping Q x E - 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 determining whether two of these machines are equivalent. Formulate this problem as a language, and show that it is undecidable.

Reference no: EM1369872

Questions Cloud

Determine monetary value of the efficiency loss : I am planning giving a patent for a new drug. The public demand is given through: P=120-10Q, where Q is quantity of the drug and P is price. If the marginal cost of production is given by MC = 2Q,

Write limitations of present windows computers : Write down some limitations of present Windows 95 and 98 computers for use in context of this library, compared to more modern operating system?

Analyzing is lm curves : Carefully describe and show graphically how each of following changes would effect the shape of the IS curve:

Computing accounting and economic profits : Jane decided to resign from her current job, at which she earned $58,000 each year. She started her own business by using her $100,000 savings on which she was earning 5 % interest. In first year, her revenue was $150,000 and her costs were as fol..

Finding whether two machines are equivalent : Consider the problem of finding whether two of these machines are equivalent. Formulate this problem as the language, and illustrate that it is undecidable.

Cost structure of perfectly competitive firm : In the perfectly competitive industry, the market price is $25. A firm is currently producing 10,000 units of output, its average total cost is $28, its marginal cost is $20, and its average variable cost is $20.

Calculate the competitive market long run equilibrium : The Hair Stylist, limited, has a monopoly in College Park market because of restrictive licensing requirements, and not because of superior operating efficiency.

Find speedup gain of using simd computer over sisd computer : If both SISD and SIMD machines run at same clock speed, determine the speedup gain of using the SIMD computer over the SISD computer?

Market structure concepts : One might expect company in monopolistically competitive market to experience greater swings in price of their products over the business cycle than those in an oligopoly market.

User Account

All Pages