q1)Let h be the homomorphism defined by h(a) = 01 and h(b) = 1. Let L1 = h({aba, bab}), that is, h applied to the language consisting of two strings, aba and bab.

(a) How many strings are there in L1?

Let L2 = h-1({010, 101}).

(b) How many strings are there in L2?

Q 2) The Turing machine M has states q, p, and f. State q is the start state, and f is the accepting state. The input alphabet is {0,1} and the tape alphabet is {0,1,B}; B is the blank. The transitions of M are:

(q,0) = (p,0,R)

(q,1) = (p,0,R)

(p,0) = (p,0,R)

(p,1) = (q,1,L)

(p,B) = (f,0,R)

(a) On input 100, M:

Accepts

Halts without accepting

Does not halt

(b) On input 001, M:

Accepts

Halts without accepting

Does not halt

(c) On input , M:

Accepts

Halts without accepting

Does not halt