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