Recursive languages:

• A language L is recursive if there exist a Turing machine T deciding L.
• A language L is Turing-decidable if there exist a Turing machine T deciding L.

• Example: {0n10n|n≥0} is a recursive language.

Closure Properties of Class of Recursive Languages

Theorem:

Let L be the recursive language over ∑. Then, L is recursive. 

Proof:

Let L be a recursive language over ∑. Then, there is a TM T computing ΧL.

Construct a tape TM M computing Χ'L. as follows:

→ T → TmoveRight  0 → Twrite1  Twrite0

Then,L is recursive.

Closure Property Under Union

Theorem: Let L1 and L2 be recursive languages over ∑. Then, L1∪L2 is recursive.

Proof:

Let L1 and L2 be recursive languages over ∑.

Then, there is TM's T1 and T2 computing ΧL1 and ΧL2, respectively. Construct a two-tape TM M as follows:

→ TcopyTape1ToTape2 → T1 → TmoveRight 0 → TcopyTape2ToTape1 → T2

Closure Property Under Union

→ TcopyTape1ToTape2 → T1 → TmoveRight 0 → TcopyTape2ToTape1  → T2

If the input w is not in L1 and L2, ΧL1(w) and ΧL2(w)=0. Thus, both T1 and T2 must run, and M stop with output 0.

If the input w is in L1, ΧL1(w)=1. Therefore, M halts with output 1.

If the input w is not in L1 but is in L2, ΧL1(w)=0 and ΧL2(w)=1. Therefore, M halts with output 1.

Which menas, M computes characteristic function of ΧL. Then, L1∪L2 is recursive.

Closure Property Under Intersection

Theorem: Let L1 and L2 be the recursive languages over S. Then, L1∩L2 is recursive in nature. 

Proof:

Let L1 and L2 be recursive languages over S.

Then, there is TM's T1 and T2 computing ΧL1 and ΧL2, respectively.

Construct a 2-tape TM M as follows:

→ TcopyTape1ToTape2 → T1 → TmoveRight 1 → TcopyTape2ToTape1 → T2

TcopyTape1ToTape2 → T1 → TmoveRight  1→ TcopyTape2ToTape1  → T2

If input w is in L1∩L2, ΧL1(w) and ΧL2(w)=1. Thus, M halts with output 1. 

If input w is not in L1, ΧL1(w)=0. Thus, M halts with output 0.

If input w is in L1 but is not in L2, ΧL1(w)=1 and ΧL2(w)=0. Thus, M halts with output 0.

This means that, M computes characteristic function of ΧL1∩L2. Then, L1∩L2 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 Closure Properties of Class of 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.