Theory of Computation

Non-Deterministic Turing Machine

In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation...

Turing Machine

A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing. Contents 1...

Pushdown Automata & Parsing

Parsing is used to derive a string using the production rules of a grammar. It is used to check the acceptability of a string. Compiler is used to check...

Pushdown Automata Introduction

Contents 1 Basic Structure of PDA 2 Terminologies Related to PDA 2.1 Instantaneous Description 2.2 Turnstile Notation 2.3 Final State Acceptability 2.4 Empty Stack Acceptability 2.5 Example 2.6 Solution...

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 be written as w...

Chomsky Normal Form

A CFG is in Chomsky Normal Form if the Productions are in the following forms − A → a A → BC S → ε where A, B, and...

CFG Simplification

In a CFG, it may happen that all the production rules and symbols are not needed for the derivation of strings. Besides, there may be some null productions and...

Context-Free Grammar

Definition − A context-free grammar (CFG) consisting of a finite set of grammar rules is a quadruple (N, T, P, S) where N is a set of non-terminal symbols....

DFA Complement

If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with...

Pumping Lemma For Regular Grammars

Pumping Lemma for Regular Languages Theorem Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L − |w| ≥...