[Solved]: Finding a function which is a mapping reduction of A to B

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

 Download Related Notes/Documents