Properties of reduction:

Theorem 1:           

Let L be a language over Σ. L≤L. Proof:

Let L be a language over Σ.

Let f be an identity function from Σ*Σ→*.

Then, there is a TM computing f.

Because f is an identity function, w∈L ↔ f(w)=w∈L. By definition, L≤L.

Theorem 2:

Let L1 and L2 be languages over Σ.

If L1≤L2, then L'1≤L2.

Proof:

Let L1 and L2 be languages over Σ.

Because L1≤L2, there is a function f that w∈L1  f(w)∈L2, and a TM T computing f.

w'∈L1 ↔ f(w)'∈L2.

By definition,'L1'≤L2.

Theorem 3:     

Let L1, L2 and L3 be languages over Σ.

If L1≤L2 and L2≤L3, then L1≤L3.

Proof:

Let L1, L2 and L3 be languages over Σ.

There is a function f such that w∈L1 ↔ f(w)∈L2, and a TM T1 computing f because L1≤L2.

There is a function g such that w∈L2 ↔ g(w)∈L3, and a TM T2 computing g as L2≤L3.

w∈L1 ↔ f(w)∈L2 ↔ g(f(w))∈L3, and T1→T2 calculates g(f(w)).

By the definition, L1≤L3.

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