Reduction Definition:

Let L1 and L2 be languages over Σ1 and Σ2, respectively. L1 is (many-one) reducible to L2, denoted by L1≤L2, if there is a TM M calculating a function f: Σ1*Σ→2* such that w∈L1 ↔ f(w)∈L2.

Definition:

Let P1 and P2 be problems.  P1 is (many-one) reducible to P2 if there is a TM M computing a function f: Σ1*Σ→2* that w is a yes-instance of P1 ↔ f(w) is a yes-instance of P2.

Reduction:

Definition:

A function f: Σ1*Σ→2* is a Turing-computable function if there is a Turing machine computing f.

Definition:

Let L1 and L2 be languages over Σ1 and Σ2, respectively. L1 is (many-one) reducible to L2, can be denoted by L1≤L2, if there is a Turing-computable function f: Σ1*Σ→2* that w∈L1 ↔ f(w)∈L2.

Meaning of Reduction

P1 is reducible to  P2 if ∃ TM M computing a function f: Σ1*Σ→2* that w is a yes-instance of P1 ↔ f(w) is a yes-instance of P2.

• If you can map yes-instances of problem A to yes-instances of problem B, then

-   we can solve A if we can solve B

-   it doesn't mean we can solve B if we can solve A

-   the decidability of B implies decidability of A

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Reduction in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.