By using reduction to prove decidability:

Theorem: If L2 is recursive, and L1≤L2, then L1 is also recursive.

proof:

Let L1 and L2 be languages over Σ, L1≤L2, and L2 be recursive. As L2 is recursive, there is a TM T2 computing ΧL2.

As L1≤L2, there is a TM T1 computing a function f such that w∈L1 ↔ f(w)∈L2.

Example:

Construct a TM T=T1→T2. We show that T computes ΧL1.

-    If w∈L1, T1 in T computes f(w)∈L2 and T2 in T computes ΧL2(f(w)), which is 1.

-    If w∈L1, T1 in T computes f(w)∈L2 and T2 in T computes ΧL2(f(w)), which is 0.

Therefore, L1 is also recursive.

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 Using reduction to prove decidability in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.