Using reduction to prove R.E:

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

Proof:

Let L1 and L2 be languages over Σ, L1≤L2, and L2 be R.E. As L2 is R.E, there is a TM T2 accepting L2. 

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

Examples:

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

-    If w∈L1, T1 in T computes f(w)∈L2 and T2 in T accepts f(w). Therefore, T accepts w.

-    If w∈L1, T1 in T computes f(w)∈L2 and T2 in T does not accept (f(w)).

Therefore, T does not accept w. Thus, L1 is also R.E.

Theorem: 

If L2 is co-R.E., and L1≤L2, then L1 is also co-R.E.

Proof:

Let L1 and L2 be languages over Σ, L1≤L2, and L2 be co-R.E. Because L2 is co-R.E,L'2 is R.E.

Because L1≤L2,L'1≤L2.  Then,L'1 is R.E. Thus, L1 is co-R.E.

Theorem: 

If L2 is co-R.E., and L1≤L2, then L1 is also co-R.E.

Proof:

Let L1 and L2 be languages over Σ, L1≤L2, and L2 be co-R.E. Because L2 is co-R.E,L'2 is R.E.

Because L1≤L2,L'1≤L2.  Then,L'1 is R.E. Thus, L1 is co-R.E.

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