## Theory of Computation – Chomsky Normal Form

There are many normal forms for CFGs. They are the forms of context free grammar which are broad enough so that any grammar has an equivalent normal form version. You may think of it as cleaning up the grammar. A context free grammar is in Chomsky normal form (CNF) if every production in the grammar … Read more

## Theory of Computation – Eliminating unit productions from the productions in the Context Free Grammar

A unit production is a production A -> B where both A and B are non-terminals. Unit productions are redundant and hence should be removed. Follow the following steps to remove the unit production Repeat the following steps while there is a unit production Select a unit production A -> B, such that there exist … Read more

## Theory of Computation – Eliminating useless symbols from the productions in a Context Free Grammar

In this tutorial we define those symbols that do not participate in derivation of any string, i.e. the useless symbols, and remove the useless productions from the grammar. A symbol X is useful if: If X is generating, i.e., X =>* w, where w ϵ L(G) and w in Vt*, this means that the string … Read more

## Theory of Computation – Eliminating null production from the productions in the Context Free Grammar

Null productions are of the form A -> ϵ. In this tutorial we will learn to remove the null productions from the grammar. We cannot remove all ϵ-productions from a grammar if the language contains ϵ as a word, but if it doesn’t we can remove all. In a given CFG, we call a non-terminal … Read more

## Theory of Computation – Regular Grammars

If all production of a CFG are of the form A -> wB or A -> w, where A and B are variables and w ϵ Vt*, then we say that grammar is right linear. If all production of a CFG are of the form A -> Bw or A -> w, we call it … Read more

## Theory of Computation – Context Free Grammars (CFG) and Context Free Languages (CFL)

In this tutorial we will introduce context free grammars and context free language. Context free languages have great practical significance. CFLs are used by the compiler in the parsing phase as they define the syntax of a programming language and are used in many editors. There are four important components in a grammatical description of … Read more

## Theory of Computation – Pumping Lemma for Regular Languages and its Application

Every regular Language can be accepted by a finite automaton, a recognizing device with a finite set of states and no auxiliary memory. This finiteness of the set is used by the pumping lemma in proving that a language is not regular. It is important to note that pumping lemma is not used for proving … Read more

## Theory of Computation – Minimizing a Deterministic Finite Automata

In this tutorial we will learn how to minimize a DFA. It is important to minimize the DFA before its implementation. This saves space taken up by unnecessary states and transitions. For any regular language there exists a DFA with smallest number of states that accepts it. The procedure below will always produce the DFA … Read more

## Theory of Computation – Conversion of Nondeterministic Finite Automata to Deterministic Finite Automata

For every nondeterministic finite automaton there exists an equivalent deterministic finite automaton. It means that for every nondeterministic finite automaton accepting a language L there exist a deterministic finite automaton that accepts the same language L. The DFA equivalent of an NFA simulates the moves of the NFA in parallel. To do that the states … Read more 