Let h be the homomorphism defined by h(a) = 01, h(b) = 10, h(c) = 0, and h(d) = 1. If we take any string w in (0+1)*, h-1(w) contains some number of strings, N(w). For example, h-1(1100) = {ddcc, dbc}, i.e., N(1100) = 2. We can calculate the number of strings in h-1(w) by a recursion on the length of w. For example, if w = 00x for some string x, then N(w) = N(0x), since the first 0 in w can only be produced from c, not from a.

Complete the reasoning necessary to compute N(w) for any string w in (0+1)*. Then, choose the correct value of N(01101).

a) 6

b) 4

c) 16

d) 8

Explain me

## Expert Answer

N (00x) = N (0X)

0 can be only produce from C only

Rule2:

N (01x) = N (1X) + N(X)

In 01 first 0 in w can only be produced from c then N (01X) = N (1X)

01 in w can be produce form a then N (01X) =N(X)

Rule 3:

N (11X) = N (1X)

In 11 First 1 in w can only be produced from d then N (11X) = N (1X)

Rule 4:

N (10X) = N (0X) + N (X)

In 10 first 1 in w can only be produced from d then N (10X) = N (0X)

10 in w can be produce form b then N (10X) =N(X)

- N(01101)=N(1101)+N(101) (applying rule 2)

=N (101) +N (101) (applying rule 3)

= 2*(N101)

N (101) = N (01) + N (1) (applying rule 4)

= N(1) + N(empty) + N(1)

= 1 + 1 + 1 = 3

N(01101) = 2* N(101)

= 2*3 =6

Those are

h-1 (01101) = {cddcd,,cdda,cdcd,adcd, adda, adcd}