Problem Detail: How do I precisely define the function which is a mapping reduction of A to B for the following examples? What is the process of figuring this out? Given: A and B are languages over the alphabet {0,1}. Examples:
- A is the language described by 1*0*, B is the language described by 01*0*
- A={w | the length of w is even}, B={w | the length of w is odd}
- A=B={w | the length of w is even}
- A={0,1}*, B={00,1,101}
I am studying this material and I am not sure of how to ‘precisely’ define these functions. Could somebody provide me with solutions and a methodology to finding the solution?
Asked By : user11622
Answered By : user11622
The answers are as follows, just functions with input w: f(w) = 0w f(w) = 0w f(w) = w f(w) = 00 Basically make sure all scenarios which occur in A are mapped to B and that all which are not, do not map to B
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18339 3.2K people like this
