# Properties of Recursively enumerable languages in theory of automata

Last modified on May 26th, 2018 at 2:04 pm

**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:

- Union
- Intersection
- 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 TM
_{n}halts then system halts

**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 TM
_{n}, and if TM2 is also halted, then system halts. - If TM1 and TM2 or TM
_{n}crash then the system crash

**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 TM
_{n}. If TM1 halts and TM2 also halts then system crash. - If TM1 halts then system check TM2 or TM
_{n}. If TM1 halts and TM2 crash then system halts.