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
1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization


A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Can v find the given number is palindrome or not using turing machine

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

turing machine for prime numbers

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