Classification Of Grammer

Acc to chomsky grammer are classified into four type:

1) Type-3 Grammer:

                A--->αB/β

               A,B ∈ V

              α,β  ∈ T*

This is also called as right linear grammer(RLG).

 

              A--->Bα/β

               A,B ∈ V

              α,β  ∈ T*

This is also called as left linear grammer(LLG).

V=variable

T=terminals

 

NOTE:- Whatever language is generated by type-3 grammer they are nothing but regular grammer.

 

2) Type-2 Grammer:(Context Free Grammer)

            A--->α  ,A ∈ V

                  α ∈(V ∪ T)*

If a grammer is regular then it is definetly context free  but if a grammer is context free then it may not be regular.

 

e.g

anbmcn+m/n,m>=1

Sol:

S--->aSc/aAc

A--->bAc/bc

 

3)Type-1 Grammer:(Context sensitive grammer)

               x--->y

               where x,y ∈ (V ∪ T) 

                and |x|=<|y|

this mean always the grammer is non contracting.

e.g:-

S--->abc/aAbc

Ab--->bA

Ac--->Bbcc

bB--->Bb

aB--->aa/aaA

laguage generating by this CSG is?

Sol:

anbncn    n>=1

        

4) Type-0 Grammer:( unrestricted Grammer)

A grammer is called unrestricted if all the production are of the form u--->v where u is in (v ∪ T)+

v is in (v ∪ T)*

v is a varible and T is a terminal

Contributor's Info

Created:
0Comment
Grammer
In the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc.

The theory of formal languages finds its applicability extensively in the fields of Computer Science. Noam Chomsky gave a mathematical model of grammar in 1956 which is effective for writing computer languages.

Contributor's Info

Created:
0Comment
Grammer | Theory of Computation
  1. Grammar has set of rules to generate the strings of a language.
  2. A grammar G can be formally written as a 4-tuple (N, T, S, P)

Where;

  • N or VN is a set of variables or non-terminal symbols.
  • T or  is a set of Terminal symbols.
  • S is a special variable called the Start symbol, S ∈ N
  • P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on VN ∪ ∑ and least one symbol of α belongs to VN.

Example:

Grammar : ({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Here,

  • S, A, and B are Non-terminal symbols;
  • a and b are Terminal symbols
  • S is the Start symbol, S ∈ N
  • Productions, P : S AB, A a, B b

Contributor's Info

Created: Edited:
0Comment