Two-tape turing machine, Theory of Computation

Assignment Help:

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."


Related Discussions:- Two-tape turing machine

Decision problems of regular languages, We'll close our consideration of re...

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Gdtr, What is the purpose of GDTR?

What is the purpose of GDTR?

#title., distinguish between histogram and historigram

distinguish between histogram and historigram

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors...

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh...

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Turing, turing machine for prime numbers

turing machine for prime numbers

Chomsky normal form, s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbo...

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd