1 1 vote 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(10100101). a) 15 b) 34 c) 128 d) 25 Algorithms recurrence-relation theory-of-computation algorithms + – Akash Kanase 709 views answer comment Share Follow Print See 1 comment 1 1 comment reply Ajay Jadhav commented Nov 5, 2016 reply Follow flag I'm getting answer as 128.Is it correct? Because each step of 2 bits there are two possible replacements 0 0 replyShare Please log in or register to add a comment.
