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
How useful is production function in production planning?

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica


Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

how to understand DFA ?