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


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
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?

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

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

i want to do projects for theory of computation subject what topics should be best.

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

How useful is production function in production planning?

Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav