Chomsky Hierarchy

Chomsky Hierarchy represents the class of languages that are accepted by the different machine. The category of language in Chomsky's Hierarchy is as given below:

1. Type 0 known as Unrestricted Grammar.
2. Type 1 known as Context Sensitive Grammar.
3. Type 2 known as Context Free Grammar.
4. Type 3 Regular Grammar.

This is a hierarchy. Therefore every language of type 3 is also of type 2, 1 and 0. Similarly, every language of type 2 is also of type 1 and type 0, etc.

Type 0 Grammar:

Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules of these types of languages. These languages can be efficiently modeled by Turing machines.

For example:

bAa → aa  

S → s  

Type 1 Grammar:

Type 1 grammar is known as Context Sensitive Grammar. The context sensitive grammar is used to represent context sensitive language. The context sensitive grammar follows the following rules:

• The context sensitive grammar may have more than one symbol on the left hand side of their production rules.
• The number of symbols on the left-hand side must not exceed the number of symbols on the right-hand side.
• The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right-hand side of any rule.
• The Type 1 grammar should be Type 0. In type 1, Production is in the form of V → T

Where the count of symbol in V is less than or equal to T.

For example:

S → AT  

T → xy  

A → a  

Type 2 Grammar:

Type 2 Grammar is known as Context Free Grammar. Context free languages are the languages which can be represented by the context free grammar (CFG). Type 2 should be type 1. The production rule is of the form

A → α  

Where A is any single non-terminal and is any combination of terminals and non-terminals.

For example:

A → aBb  

A → b  

B → a  

Type 3 Grammar:

Type 3 Grammar is known as Regular Grammar. Regular languages are those languages which can be described using regular expressions. These languages can be modeled by NFA or DFA.

Type 3 is most restricted form of grammar. The Type 3 grammar should be Type 2 and Type 1. Type 3 should be in the form of

V → T*V / T*  

For example:

A → xy  

Greibach Normal Form (GNF)

GNF stands for Greibach normal form. A CFG(context free grammar) is in GNF(Greibach normal form) if all the production rules satisfy one of the following conditions:

• A start symbol generating ε. For example, S → ε.
• A non-terminal generating a terminal. For example, A → a.
• A non-terminal generating a terminal which is followed by any number of non-terminals. For example, S → aASB.

For example:

G1 = {S → aAB | aB, A → aA| a, B → bB | b}  

G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}  

The production rules of Grammar G1 satisfy the rules specified for GNF, so the grammar G1 is in GNF. However, the production rule of Grammar G2 does not satisfy the rules specified for GNF as A → ε and B → ε contains ε(only start symbol can generate ε). So the grammar G2 is not 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. You can refer the following topic to convert the CFG into CNF: Chomsky normal form

Step 2: If the grammar exists left recursion, eliminate it.

If the context free grammar contains left recursion, eliminate it. You can refer the following topic to eliminate left recursion: Left Recursion

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.

Example:

S → XB | AA  

A → a | SA  

B → b  

X → a  

Solution:

As the given grammar G is already in CNF and there is no left recursion, so we can skip step 1 and step 2 and directly go to step 3.

The production rule A → SA is not in GNF, so we substitute S → XB | AA in the production rule A → SA as:

S → XB | AA  

A → a | XBA | AAA  

B → b  

X → a  

The production rule S → XB and B → XBA is not in GNF, so we substitute X → a in the production rule S → XB and B → XBA as:

S → aB | AA  

A → a | aBA | AAA  

B → b  

X → a  

Now we will remove left recursion (A → AAA), we get:

S → aB | AA  

A → aC | aBAC  

C → AAC |  ε  

B → b  

X → a  

Now we will remove null production C → ε, we get:

S → aB | AA  

A → aC | aBAC | a | aBA  

C → AAC |  AA  

B → b  

X → a  

The production rule S → AA is not in GNF, so we substitute A → aC | aBAC | a | aBA in production rule S → AA as:

S → aB | aCA | aBACA | aA | aBAA  

A → aC | aBAC | a | aBA  

C → AAC  

C → aCA | aBACA | aA | aBAA  

B → b  

X → a  

The production rule C → AAC is not in GNF, so we substitute A → aC | aBAC | a | aBA in production rule C → AAC as:

S → aB | aCA | aBACA | aA | aBAA  

A → aC | aBAC | a | aBA  

C →  aCAC | aBACAC | aAC | aBAAC  

C → aCA | aBACA | aA | aBAA  

B → b  

X → a  

Hence, this is the GNF form for the grammar G.

Chomsky's Normal Form (CNF)

CNF stands for Chomsky normal form. A CFG(context free grammar) is in CNF(Chomsky normal form) if all production rules satisfy one of the following conditions:

• Start symbol generating ε. For example, A → ε.
• A non-terminal generating two non-terminals. For example, S → AB.
• A non-terminal generating a terminal. For example, S → a.

For example:

G1 = {S → AB, S → c, A → a, B → b}  

G2 = {S → aA, A → a, B → c}  

The production rules of Grammar G1 satisfy the rules specified for CNF, so the grammar G1 is in CNF. However, the production rule of Grammar G2 does not satisfy the rules specified for CNF as S → aZ contains terminal followed by non-terminal. So the grammar G2 is not in CNF.

Steps for converting CFG into CNF

Step 1: Eliminate start symbol from the RHS. If the start symbol T is at the right-hand side of any production, create a new production as:

S1 → S  

Where S1 is the new start symbol.

Step 2: In the grammar, remove the null, unit and useless productions. You can refer to the Simplification of CFG.

Step 3: Eliminate terminals from the RHS of the production if they exist with other non-terminals or terminals. For example, production S → aA can be decomposed as:

S → RA  

R → a  

Step 4: Eliminate RHS with more than two non-terminals. For example, S → ASB can be decomposed as:

S → RS  

R → AS  

Example:

Convert the given CFG to CNF. Consider the given grammar G1:

S → a | aA | B  

A → aBB | ε  

B → Aa | b  

Solution:

Step 1: We will create a new production S1 → S, as the start symbol S appears on the RHS. The grammar will be:

S1 → S  

S → a | aA | B  

A → aBB | ε  

B → Aa | b  

Step 2: As grammar G1 contains A → ε null production, its removal from the grammar yields:

S1 → S  

S → a | aA | B  

A → aBB  

B → Aa | b | a  

Now, as grammar G1 contains Unit production S → B, its removal yield:

S1 → S  

S → a | aA | Aa | b  

A → aBB  

B → Aa | b | a  

Also remove the unit production S1 → S, its removal from the grammar yields:

S0 → a | aA | Aa | b  

S → a | aA | Aa | b  

A → aBB  

B → Aa | b | a 

Step 3: In the production rule S0 → aA | Aa, S → aA | Aa, A → aBB and B → Aa, terminal a exists on RHS with non-terminals. So we will replace terminal a with X:

S0 → a | XA | AX | b  

S → a | XA | AX | b  

A → XBB  

B → AX | b | a  

X → a  

Step 4: In the production rule A → XBB, RHS has more than two symbols, removing it from grammar yield:

S0 → a | XA | AX | b  

S → a | XA | AX | b  

A → RB  

B → AX | b | a  

X → a  

R → XB  

Hence, for the given grammar, this is the required CNF.

Simplification of CFG

As we have seen, various languages can efficiently be represented by a context-free grammar. All the grammar are not always optimized that means the grammar may consist of some extra symbols(non-terminal). Having extra symbols, unnecessary increase the length of grammar. Simplification of grammar means reduction of grammar by removing useless symbols. The properties of reduced grammar are given below:

1. Each variable (i.e. non-terminal) and each terminal of G appears in the derivation of some word in L.
2. There should not be any production as X → Y where X and Y are non-terminal.
3. If ε is not in the language L then there need not to be the production X → ε.

Removal of Useless Symbols

A symbol can be useless if it does not appear on the right-hand side of the production rule and does not take part in the derivation of any string. That symbol is known as a useless symbol. Similarly, a variable can be useless if it does not take part in the derivation of any string. That variable is known as a useless variable.

For Example:

T → aaB | abA | aaT  

A → aA  

B → ab | b  

C → ad  

In the above example, the variable 'C' will never occur in the derivation of any string, so the production C → ad is useless. So we will eliminate it, and the other productions are written in such a way that variable C can never reach from the starting variable 'T'.

Production A → aA is also useless because there is no way to terminate it. If it never terminates, then it can never produce a string. Hence this production can never take part in any derivation.

To remove this useless production A → aA, we will first find all the variables which will never lead to a terminal string such as variable 'A'. Then we will remove all the productions in which the variable 'B' occurs.

Elimination of ε Production

The productions of type S → ε are called ε productions. These type of productions can only be removed from those grammars that do not generate ε.

Step 1: First find out all nullable non-terminal variable which derives ε.

Step 2: For each production A → a, construct all production A → x, where x is obtained from a by removing one or more non-terminal from step 1.

Step 3: Now combine the result of step 2 with the original production and remove ε productions.

Example:

Remove the production from the following CFG by preserving the meaning of it.

S → XYX  

X → 0X | ε  

Y → 1Y | ε  

Solution:

Now, while removing ε production, we are deleting the rule X → ε and Y → ε. To preserve the meaning of CFG we are actually placing ε at the right-hand side whenever X and Y have appeared.

Let us take

S → XYX  

If the first X at right-hand side is ε. Then

S → YX  

Similarly if the last X in R.H.S. = ε. Then

S → XY  

If Y = ε then

S → XX  

If Y and X are ε then,

S → X  

If both X are replaced by ε

S → Y  

Now,

S → XY | YX | XX | X | Y  

Now let us consider

X → 0X  

If we place ε at right-hand side for X then,

X → 0  

X → 0X | 0  

Similarly Y → 1Y | 1

Collectively we can rewrite the CFG with removed ε production as

S → XY | YX | XX | X | Y  

X → 0X | 0  

Y → 1Y | 1  

Removing Unit Productions

The unit productions are the productions in which one non-terminal gives another non-terminal. Use the following steps to remove unit production:

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 step 2 until all unit productions are removed.

For example:

S → 0A | 1B | C  

A → 0S | 00  

B → 1 | A  

C → 01  

Solution:

S → C is a 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  

Similarly, B → A is also a unit production so we can modify it as

B → 1 | 0S | 00  

Thus finally we can write CFG without unit production as

S → 0A | 1B | 01  

A → 0S | 00  

B → 1 | 0S | 00  

C → 01  

Conversion of RE to FA

To convert the RE to FA, we are going to use a method called the subset method. This method is used to obtain FA from the given regular expression. This method is given below:

Step 1: Design a transition diagram for given regular expression, using NFA with ε moves.

Step 2: Convert this NFA with ε to NFA without ε.

Step 3: Convert the obtained NFA to equivalent DFA.

Example 1:

Design a FA from given regular expression 10 + (0 + 11)0* 1.

Solution: First we will construct the transition diagram for a given regular expression.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Now we have got NFA without ε. Now we will convert it into required DFA for that, we will first write a transition table for this NFA.

State	0	1
→q0	q3	{q1, q2}
q1	qf	ϕ
q2	ϕ	q3
q3	q3	qf
*qf	ϕ	ϕ

The equivalent DFA will be:

State	0	1
→[q0]	[q3]	[q1, q2]
[q1]	[qf]	ϕ
[q2]	ϕ	[q3]
[q3]	[q3]	[qf]
[q1, q2]	[qf]	[qf]
*[qf]	ϕ	ϕ

Example 2:

Design a NFA from given regular expression 1 (1* 01* 01*)*.

Solution: The NFA for the given regular expression is as follows:

Step 1:

Step 2:

Step 3:

Example 3:

Construct the FA for regular expression 0*1 + 10.

Solution:

We will first construct FA for R = 0*1 + 10 as follows:

Step 1:

Step 2:

Step 3:

Step 4: