This article explores a step-by-step approach to convert any context-free grammar to a context-free grammar in Chomsky Normal Form.
Continue readingPost Category → Theoretical Computer Science
Regular Grammars
This article discusses the concept of Regular Grammars and their equivalence with NFAs. Conversion examples included.
Continue readingContext-Free Grammar – Formal Definition and Observations
A short primer on the formal definition of a context-free grammar followed by few observations.
Continue readingProving a Language is not Regular using the Pumping Lemma – String Choices
This article explores a step by step approach to prove that a language is not regular by using a combination of Closure Properties and the Pumping Lemma.
Continue readingProving a Language is not Regular using the Pumping Lemma
This article explores, with the help of figures, a step by step approach to prove that a language is not regular by contradicting the Pumping Lemma for Regular languages.
Continue readingVisualizing the Pumping Lemma for Regular Languages – Splitting into Substrings
This article explains how to read the Pumping Lemma conditions by visualizing the breaking of a string into three substrings. A blueprint to use this Lemma to prove a language is not regular is discussed.
Continue readingConverting an NFA to an equivalent Regular Expression – the GNFA method
The GNFA method is a procedure to rip out states from an NFA one by one to produce an equivalent regular expression. This article takes an example and explains each step through detailed figures.
Continue readingConverting an NFA to an equivalent DFA
Both deterministic and non-deterministic finite machines recognize the set of regular languages. This article explores a step by step approach to convert a NFA to a DFA that accepts the same language through detailed examples.
Continue readingConverting a Regular Expression to an equivalent NFA
A step-by-step approach to convert a regular expression to an equivalent NFA. Basic 6 cases are explained followed by a complex expression example.
Continue readingConstructing the Cross-Product of 2 DFAs
A step-by-step visual approach to construct the Cross-Product of two DFAs to create the union and intersection of two languages.
Continue reading