The equivalence of regular languages is decidable. Here is how.
Continue readingPost Category → Theoretical Computer Science
Decidable Languages : EDFA, ENFA, EREX, ERG
Checking whether a regular language is empty is decidable. Here is how.
Continue readingDecidable Languages : ADFA, ANFA, AREX, ARG
Checking whether a string belongs to a regular language is decidable. Here is how.
Continue readingString Encoding of Machines – What is <M>?
What is <M>? A short discussion of encoding machines as strings.
Continue readingTuring Machine Variant – Nondeterminism
Non deterministic turing machines and their equivalence to single-tape turing machines. Computation tree and address mapping discussed.
Continue readingTuring Machine Variant – Multiple Tapes
Multitape turing machines and their equivalence to single-tape turing machines.
Continue readingTuring Recognizable, Turing Decidable and Turing Enumerable
A clear explanation of Turing Recognizable, Decidable and Enumerable languages and the relationships between them.
Continue readingTuring 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 readingHigh-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 readingLow-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