Soggadu telugu comedy short film by HanumanthaRao Nagula

CLASSIFICATION OF GRAMMAR - NOAM CHOMSKY'S || FINITE AUTOMATA THEORY

NOAM CHOMSKY’S CLASSIFICATION OF GRAMMARS

Grammars are categorized by the productions that define them. The four types of grammars, due to Chomsky (who developed the theory of formal languages), are referred to as the ‘Chomsky hierarchy of grammars’.

Let G= (V,T,P,S) be a grammar. Let A,B V and α,α’, €(V )^* Here ,α,α’ and ’ could be null word.

Phrase-Structured grammar (Recursively Enumerable)

·         Any phrase-structured grammar (or unrestricted grammar) is type 0. G is said to be type0, if all the productions are from α->  where  € (V )^* and α € (V )⁺

·         Clearly, it is seen that α cannot be  € ,which means that no €  can be on left side of any production. However, € can appear on the right hand side of any production.

·         A language L(G) is recursively enumerable (or type0), if the grammar G is of type0.

·         The language recognizer in this case it is turning machine.

Example (Type0 grammar)

             S->aBb/€

ab->bBB

bB->ab

Context-Sensitive grammar:

·         G is context-sensitive (type1) if every production is of the form α ,where  α,  € (V )⁺

·         Clearly it is seen that α and   cannot be €  , which means that no  € appears on the left and right hand sides of any production . thus this grammar is € -free.

·         A language L(G) is context-sensitive (or type1), if the grammar G is context sensitive.

·         The language recognizer in this case is linear-bounded automata.

Example:

              S->aBb

aB->bBB

bB->ab

The venn diagram below clearly shows the Chomsky hierarchy of various grammars:

Chomsky Classification of Grammars

According to Noam Chomosky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other −

Grammar Type	Grammar Accepted	Language Accepted	Automaton
Type 0	Unrestricted grammar	Recursively enumerable language	Turing Machine
Type 1	Context-sensitive grammar	Context-sensitive language	Linear-bounded automaton
Type 2	Context-free grammar	Context-free language	Pushdown automaton
Type 3	Regular grammar	Regular language	Finite state automaton

Take a look at the following illustration. It shows the scope of each type of grammar

Type - 3 Grammar : Type-3 grammars generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.

The productions must be in the form X → a or X → aY

where X, Y ∈ N (Non terminal) and a ∈ T (Terminal)

The rule S → ε is allowed if S does not appear on the right side of any rule.

Example

X → ε

X → a | aY

Y → b

Type - 2 Grammar: Type-2 grammars generate context-free languages.

The productions must be in the form A → γ where A ∈ N (Non terminal) and γ ∈ (T ∪ N)* (String of terminals and non-terminals).

These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.

Example :

S → X a

X → a

X → aX

X → abc

X → ε

Type - 1 Grammar : Type-1 grammars generate context-sensitive languages. The productions must be in the form

α A β → α γ β

where A ∈ N (Non-terminal)

and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals)

The strings α and β may be empty, but γ must be non-empty.

The rule S → ε is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.

Example

AB → AbBc

A → bcA

B → b

Type - 0 Grammar : Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.

They generate the languages that are recognized by a Turing machine.

The productions can be in the form of α → β where α is a string of terminals and nonterminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.

Example

S → ACaB

Bc → acB

CB → DB

aD → Db 

AMBIGUOUS AND UNAMBIGUOUS GRAMMARS || Context Free Grammar- Formal Languages Automata Theory

·         A CFG is ambiguous, if for at least one word in its CFL, there are two possible derivations of the word that correspond to two different syntax or parse trees.

·          A grammar is said to be ambiguous, if its language contains some string that has two different parse trees.

·         A grammar is said to be unambiguous, if its language has exactly one parse tree.

·         If grammar G is ambiguous, then for some w in L(G),there exists more than one parse tree. Hence, there is more than left most order of derivation and equivalently, there is more than one right most order of derivation.

·         If grammar G is ambiguous, then for some w in L(G),there exists more than one parse tree. Hence, there is more than left most order of derivation and equivalently one right most order of derivation.

Note : A grammar is ambiguous if there are more than one left most (or right most) derivation for given w.

Example:

a.   Consider a grammar for arithmetic expressions:

          E->a\b

          E->E-E

This grammar is ambiguous, because, to derive the string w=a-b-a, there exist two distinct parse trees, as shown in figure:

Fig:  Two distinct parse trees for the derivations of string w=a-b-a.

There are two distinct parse trees, which means that there are two distinct left or right most derivations.

Left most derivations:

(i)          E E-E a-E-E a-b-E a-b-a.

(ii)         E E-E E-E-E a-E-E a-b-E a-b-a

The same is the case with right most derivation.

a.   Consider the grammar

            S->aS/a where   V={S} and T= {a}.

This grammar is unambiguous because to derive the string w=aa, there exists exactly one parse tree, as shown in figure :

There is exactly one parse tree and hence, exactly one left most or right most derivation.

    Left most derivation: S a S aa.

    Right most derivation: S a S aa.

TYPES OF GRAMMARS || Formal Languages Automata Theiry

TYPES OF GRAMMARS:

Linear and Non Linear Grammars:

A grammar is said to be linear if all its productions contain atmost one variable at the Right Hand Side, otherwise it is a non linear grammar

Example:

(i)     S -> aSb

        S -> e

Is a linear grammar

(ii)    S -> Ab

        A -> aAb

Is a linear grammar

(iii)    S -> SS

        S ->e

Is a non linear grammar

(iv)   S -> aA

        A ->b

Is a non linear grammar

Right Linear Grammar:

A Grammar is said to be right linear if its productions are of the form

                A -> xB

                Or

                A ->x

Where A, B are variables and x is a terminal

Example:   S -> abS

                S -> a

Left Linear Grammar:

A Grammar is said to be left linear if its productions are of the form

                A -> Bx

                Or

                A ->x

Where A, B are variables and x is a terminal

Example:   S -> Aab

                A -> ab/B

Regular Grammar:

A grammar is said to be regular if it is either right linear or left linear, otherwise it is a non regular grammar.

Example:   S -> abS

                S -> a

Example for Non regular grammar:        S -> aAb

                                        A -> aS

                                        B -> a

Recursive Grammar:

A grammar is said to be recursive if it contains atleast one recursive production or indirectly recursive production.

Recursive Production:    S -> aS

Indirectly Recursive Production:    S -> aA

                                                        A -> abS