Theory

A grammar is a set of production rules which are used to generate strings of a language.

We can converts context-free grammars to different normal forms.

Chomsky normal form (CNF)

Greibach normal form (GNF)

Simplifying Context Free Grammars

By simplifying CFGs we remove all the redundant productions from a grammar , while keeping the transformed grammar equivalent to the original grammar. Two grammars are called equivalent if they produce the same language. Simplifying CFGs is necessary to later convert them into Normal forms.

Types of redundant productions

Useless productions

Null productions

Unit production

Useless productions

The productions that can never take part in derivation of any string , are called useless productions. Similarly , a variable that can never take part in derivation of any string is called a useless variable.

S -> abS | abA | abB

A -> cd

B -> aB

C -> dc

production ‘C -> dc’ is useless because the variable ‘C’ will never occur in derivation of any string. The other productions are written in such a way that variable ‘C’ can never reached from the starting variable ‘S’.

Production ‘B ->aB’ is also useless because there is no way it will ever terminate . If it never terminates , then it can never produce a string. Hence the production can never take part in any derivation.

To remove useless productions , we first find all the variables which will never lead to a terminal string such as variable ‘B’. We then remove all the productions in which variable ‘B’ occurs. So the modified grammar becomes –

S -> abS | abA A -> cd C -> dc

Try to identify all the variables that can never be reached from the starting variable such as variable ‘C’. We then remove all the productions in which variable ‘C’ occurs. The grammar below is now free of useless productions –

Unit productions

The productions of type ‘X -> Y’ are called unit productions.

Step 1 − To remove X->Y add production X->a to the grammar rule whenever Y->a occurs in the grammar.

Step 2 − Now delete X->Y from the grammar

Step 3 − Repeat Step 1 and 2 until all unit productions are removed

Example:

S->0A|1B|C

A->0S|00

B->1|A

C->01>

step1:

S->C is unit production but while removing S->C we have to consider what C gives so we can add a rule to S.

S->0A|1B|01

Step 2:

B->A is also unit production

B->1|0S|00

we can write CFG without unit production as follows −

S->0A|1B|01

A->0S|00

B->1|0S|00

C->01

Chomsky normal form (CNF)

A context free grammar is in chomsky normal form if every rule is of the form

A ->BC

A ->a

where a is any terminal and A,B are any non-terminals (variables) execpt that B and C may not be the start variable. in addition we permit the rule S-> ε,where S is the start variable

Greibach normal form (CNF)

A Context Free Grammar (CFG) is said to be in Greibach Normal Form(GNF), if production rules satisfy one of the following criteria −

Only a start symbol can generate ε. For example, if S is the start symbol then S → ε is in GNF.

A non-terminal can generate a terminal. For example, if A is Non terminal and a is terminal then, A → a is in GNF.

A non-terminal can generate a terminal followed by any number of non-terminals. For Example, S → aAS is in GNF.

Steps for converting CFG into GNF

Step 1 − Convert the grammar into CNF. If the given grammar is not in CNF, convert it into CNF.

Step 2 − If the grammar consists of left recursion, eliminate it. If the context free grammar contains any left recursion, eliminate it.

Step 3 − In the grammar, convert the given production rule into GNF form. If any production rule in the grammar is not in GNF form, convert it.