Chomsky Hierarchy in Theory of Computation
According to Chomsky hierarchy, grammars are divided of 4 types:
Type 0 known as unrestricted grammar.
Type 1 known as context sensitive grammar.
Type 2 known as context free grammar.
Type 3 Regular Grammar.
Type 0: Unrestricted Grammar:
In Type 0
Type-0
grammars include all formal grammars. Type 0 grammar language are
recognized by turing machine. These languages are also known as the
Recursively Enumerable languages.
Grammar Production in the form of
where
is ( V + T)* V ( V + T)*
V : Variables
T : Terminals.
is ( V + T )*.
In type 0 there must be at least one variable on Left side of production.
For example,
Sab –> ba
A –> S.
Here, Variables are S, A and Terminals a, b.
Type 1: Context Sensitive Grammar)
Type-1 grammars generate the context-sensitive languages. The language generated by the grammar are recognized by the Linear Bound Automata
In Type 1
I. First of all Type 1 grammar should be Type 0.
II. Grammar Production in the form of
|| <= ||
i.e count of symbol in is less than or equal to
For Example,
S –> AB
AB –> abc
B –> b
Type 2: Context Free Grammar:
Type-2 grammars generate the context-free languages. The language generated by the grammar is recognized by a Pushdown automata.
In Type 2,
1. First of all it should be Type 1.
2. Left hand side of production can have only one variable.
|| = 1.
Their is no restriction on .
For example,
S –> AB
A –> a
B –> b
Type 3: Regular Grammar:
Type-3
grammars generate regular languages. These languages are exactly all
languages that can be accepted by a finite state automaton.
Type 3 is most restricted form of grammar.
Type 3 should be in the given form only :
V –> VT / T (left-regular grammar)
(or)
V –> TV /T (right-regular grammar)
for example:
S –> a
The above form is called as strictly regular grammar.
There is another form of regular grammar called extended regular grammar. In this form :
V –> VT* / T*. (extended left-regular grammar)
(or)
V –> T*V /T* (extended right-regular grammar)
for example :
S –> ab.
0 Comments