![Chomsky Hierarchy](/wp-content/uploads/2022/12/ChomskyHierarchy.png)
Chomsky Hierarchy of Language
According to Chomsky Hierarchy, language is classified as follows:
Type 0 – Unrestricted grammar.
Type 1 – Context-sensitive grammar.
Type 2 – Context-free grammar.
Type 3 – Regular Grammar.
Type 0:
- All formal grammars fall under type-0 grammars.
- The Turing machine can detect languages with type 0 grammar.
- The Recursively Enumerable languages are another name for these languages.
Type 0 Language Production in the form of α (alpha) to β (beta) 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 the Left side of production.
For example:
Sab -> ba
A -> S
Here, A, S are Variables
and a, b are Terminals
Type 1:
- It is also known as Context Sensitive Language.
- It is recognized by the Linear Bound Automata.
According to the following rules, context-sensitive grammar:
- It should be Type 0
- Multiple symbols may be present on the left side of the production rules for the context-sensitive grammar.
- The number of symbols on the left side cannot be more than the number of symbols on the right 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.
- In type 1, Production is in the form of |α| <= |β| Where the count of symbol in α is less than or equal to β.
- Also β ∈ (V + T)+ i.e. β can not be ε
For Example:
S -> AB
AB -> abc
B -> b
Type 2:
- It should be Type 1
- It is Context-Free Grammar (CFG)
- It is recognized by a Pushdown automata
- The left-hand side of production can have only one variable and there is no restriction on β (right side)
- The production rule is of the form |α| = 1.
For example:
S -> AB
A -> a
B -> b
Type 3:
- It should be Type 2
- It is a Regular Grammar
- It can be accepted by a finite-state automaton.
- It is the most restricted form of grammar.
- It can be described using regular expressions.
- These languages can be modelled by NFA or DFA.
It 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 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
#cfg #chomsky hierarchy #context free grammar #context sensitive grammar #push-down automata #turing maching #type 0 #type 1 #type 2 #type 3