A look into different Turing Machine transitions and how they affect the tape. Notations explained.
Continue readingPost Category → Theoretical Computer Science
Turing Machine – Formal Definition and Observations
The formal definition of a Turing Machine and some observations are discussed.
Continue readingProving a Language is not Regular using Closure Properties
This article explores a step by step approach to prove that a language is not regular by using the Closure Properties of Regular languages.
Continue readingDeterministic PushDown Automaton transitions
This article explores the limitations of Deterministic PushDown Automaton (DPDA) transitions to ensure determinism.
Continue readingClosure Properties of Context-Free Languages
Proofs for closure of Context-Free Languages (CFL) under Union, Concatenation, Star, Reversal, Prefix and Subsequence.
Continue readingConverting a PushDown Automaton to a Context-Free Grammar
The article discusses, with the help of an example, a step-by-step approach to convert a Pushdown Automaton (PDA) to a Context-Free Grammar (CFG).
Continue readingConverting a Context-Free Grammar to a PushDown Automaton
The article discusses, with the help of an example, a step-by-step approach to convert a Context-Free Grammar (CFG) to a Pushdown Automaton (PDA).
Continue readingExtended PushDown Automaton transitions
A short examination of extended PushDown Automaton transitions and their equivalence with PushDown Automaton transitions.
Continue readingPushDown Automaton transitions
This article discusses the different transition scenarios in a Pushdown Automaton with respect to reading the input and modifying the stack.
Continue readingContext-Free Grammars and Parse Trees
This article discusses the concept of ambiguity using parse-trees. Observations about parse-trees for grammars in Chomsky Normal Form are also mentioned.
Continue reading