Posted inTheory of Computation
Accepted Language & Decided Language
A TM accepts a language if it enters into a final state for any input…
Posted inTheory of Computation
Pushdown Automata & Parsing
Parsing is used to derive a string using the production rules of a grammar. It…
Posted inTheory of Computation
Turing Machine
A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated…
Posted inTheory of Computation
Pumping Lemma for CFG
Lemma If L is a context-free language, there is a pumping length p such that any string w ∈ L of length ≥ p can…
Posted inTheory of Computation
CFG Simplification
In a CFG, it may happen that all the production rules and symbols are not…
Posted inTheory of Computation
CFL Closure Property
Context-free languages are closed under − UnionConcatenationKleene Star operation Union Let L1 and L2 be two context free languages.…
Posted inTheory of Computation
Difference between Pushdown Automata and Finite Automata
Pushdown Automata:A Pushdown automata (PDA) is a finite state machine with an added stack storage.…
Posted inTheory of Computation
Pushdown Automata Acceptance by Final State
We have discussed Pushdown Automata (PDA) and its acceptance by empty stack article. Now, in this article,…