Properties of Recursively enumerable languages in theory of automata

What is recursively enumerable language?

If any Turing Machine can be designed to accept all string of the given language, then the language is called recursively enumerable language. RE languages are the formal languages.

Properties of Recursively enumerable languages:

  1. Union
  2. Intersection
  3. Complement

1.Union of RE languages:

Lets revise union of sets;

Set 1={a, b, c}

Set 2={b, c, d}

Set 1 Union Set 2 = {a, b, c, d}

 

Now let’s understand the same concept in Turing Machine;

Suppose a system has 2 Turing Machines, TM1, and TM2.

  • If TM1 halts then all the system halts.
  • If TM1 crash then system checks that TM2 is ready to halt or not? If TM2 halts then system halts because this is union and the union means that
    • If TM1 halts then system halts
    • If TM1 does not halt, and TM2 halts then system halts
    • If TM1 and TM2 or TMn halts then system halts

 

 

Recursive enumerable languages
Figure: Union of RE languages

2. The intersection of RE languages:

Let’s revise intersection of sets;

Set 1={a, b, c}

Set 2={b, c, d}

Set 1 Intersection Set 2 = {b, c}

 

Now let’s understand the same concept in Turing Machine;

Suppose a system has 2 Turing Machines, TM1, and TM2.

  • If TM1 crash then all the system crash.
  • If TM1 halts then system checks that TM2 is ready to halt or not? After this, If TM2 halts then system halts because this is intersection and the intersection means that
    • If TM1 crash then system crash
    • If TM1 halts then check TM2 or TMn, and if TM2 is also halted, then system halts.
    • If TM1 and TM2 or TMn crash then the system crash
turing machine 1 intersection turing machine 2
Figure: Intersection of Recursive Enumerable languages

2. The complement of RE languages:

Suppose a system has 2 Turing Machines, TM1, and TM2.

  • If TM1 crash then all the system crash.
  • If TM1 halts then system check TM2 or TMn. If TM1 halts and TM2 also halts then system crash.
  • If TM1 halts then system check TM2 or TMn. If TM1 halts and TM2 crash then system halts.
compliment of Recursively RE languages
Figure: Complement of recursively enumerable languages