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