Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too.
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.
8.3 b)
Let L1 and L2 be recognizable languages with the corresponding recognizers M1 and M2 . We construct a recognizer M for L1 ∪ L2 .
Strategy I: run M1 and M2 in parallel on a 2-tape TM M
M = "On input x:
1. Copy x on the second tape.
2. Do one step of M1 on tape 1 and one step of M2 on tape 2.
3. If either M1 or M2 accepted, then M accepts, else goto 2."
Strategy II: nondeterministically choose to run M1 or M2
M = "On input x:
1. Nondeterministically choose i ∈ {1, 2}.
2. Run machine Mi on the input x.
3. If Mi accepted, then M accepts.
If Mi rejected, then M rejects."