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
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
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
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
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
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
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
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
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
We know that for every regular expression there exist a deterministic finite automaton. So we can say that regular languages, regular expressions and finite automata are all different representation of the same thing. Earlier we learnt how to convert a regular expression into a finite automaton; in this tutorial we will learn how to convert … Read more
