Two-tape turing machine, Theory of Computation

Let there L1 and L2 . We show that L1 ∩ L2 is CFG .

Let M1 be a decider for L1 and M2 be a decider for L2 .

Consider a 2-tape TM M:

"On input x:

1. copy x on the second tape

2. on the ?rst tape run M1 on x

M=

3. if M1 accepted then goto 4. else M rejects

4. on the second tape run M2 on x

5. if M2 accepted then M accepts else M rejects."

The machine M is a decider and it accepts a string x i? both M1 and M2 accept x.

Two-tape TM is as expressive as the single tape TM.

The process is as follows

"Given a CFG G and a string w , does G generate w ?

Language Formulation (Acceptance Problem for CFG) def

ACFG = {?G , w ? | G is a CFG, w a string and w ∈ L(G )}

The language ACFG is decidable.

 Construct a decider M for ACFG :M = " 1. On input x check if x = ?G , w ? where

G is an CFG and w is a string, if not then M rejects.

2. Convert G into Chomsky normal form.

3. List all derivations in G of length exactly 2|w | - 1,

if w = ? then check if there is the rule S → ?.

4. If w is ever generated then M accepts, else M rejects."

Posted Date: 2/23/2013 12:51:23 AM | Location : United States







Related Discussions:- Two-tape turing machine, Assignment Help, Ask Question on Two-tape turing machine, Get Answer, Expert's Help, Two-tape turing machine Discussions

Write discussion on Two-tape turing machine
Your posts are moderated
Related Questions
For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

automata of atm machine

Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of


Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhMinimum 100 words accepted#

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa


It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via