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
Fazal Rehman Shamil
Welcome to all friends. The reason for our success is only your love for T4Tutorials. Our team is always available to answer your queries regarding any kind of confusions or discussion regarding your study and career matters. For discussion with us please join our facebook group "T4Tutorials.com". The link of the group is mentioned below. Thanks and love to all for connecting with us. We are nothing without you. Love you all.....
https://web.facebook.com/groups/2066136233601097/