The equivalence of regular languages is decidable. Here is how.

Continue reading# Post Category → Theoretical Computer Science

# Decidable Language : EQ

#
Decidable Languages : E_{DFA}, E_{NFA}, E_{REX}, E_{RG}

Checking whether a regular language is empty is decidable. Here is how.

Continue reading#
Decidable Languages : A_{DFA}, A_{NFA}, A_{REX}, A_{RG}

Checking whether a string belongs to a regular language is decidable. Here is how.

Continue reading# String Encoding of Machines – What is <M>?

What is <M>? A short discussion of encoding machines as strings.

Continue reading# Turing Machine Variant – Nondeterminism

Non deterministic turing machines and their equivalence to single-tape turing machines. Computation tree and address mapping discussed.

Continue reading# Turing Machine Variant – Multiple Tapes

Multitape turing machines and their equivalence to single-tape turing machines.

Continue reading# Turing Recognizable, Turing Decidable and Turing Enumerable

A clear explanation of Turing Recognizable, Decidable and Enumerable languages and the relationships between them.

Continue reading# Turing Machines Configurations

The concept of configurations of a Turing Machine and how they change based on different transitions. The notion of computation is also discussed.

Continue reading# High-level Description of a Turing Machine

A worked-out example of a high-level (implementat) description of a Turing Machine to recognize a language.

Continue reading# Low-level Description of a Turing Machine

A worked-out example of a low-level (formal) description of a Turing Machine to recognize a language.

Continue reading