Relationship Between the Classes of Recursively Enumerable and Recursive Languages:

Theorem: If L is a recursive language, then L is recursively enumerable.

Proof:

Let L be a recursive language over Σ.

Then, there is a TM T deciding L.

Then, T accepts L.

Therefore, L is recursively enumerable.

Relationship between RE and Recursive Languages:

Theorem: Let L be a language. If L and L are recursively enumerable, then L is recursive.

Proof:

Let L and'L be recursively-enumerable languages over Σ.

Then, there are a TM T accepting L, and  a TM'T accepting'L. For any string w in Σ*, w is either in L or in'L.

That is, either T or'T must halt on w, for any w in Σ*. We construct an NTM M as follows:

If w is in L, T halts on w and therefore, M accepts w.

If w is not in L,'T halts on w and therefore, M rejects w.

Then, M calculates the characteristic function of L.  Then, L is 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 Relationship between RE and Recursive Languages in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.