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