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}