As per the Noam Chomosky, four types of grammars are there including − 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|
Let’s take a look at the following diagram. It shows the scope of each type of grammar −
Type-3 grammars usually create regular languages. Type-3 grammars should have a single non-terminal on the left-hand side and a right-hand side which includes a single terminal or single terminal followed by a single non-terminal.
Make sure that 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.
Type-2 grammars usually create context-free languages.
Make sure that the productions must be in the form A → γ
where A ∈ N (Non terminal)
and γ ∈ (T ∪ N)* (String of terminals and non-terminals).
However these languages generated by these grammars are mostly recognized by a non-deterministic pushdown automaton.
While, Type-1 grammars create context-sensitive languages. Make sure that 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 β might be null, but γ must be non-empty.
The rule S → ε is accepted when S does not appear on the right side of any rule. The languages created by these grammars are found by a linear bounded automaton.
Type-0 grammars create recursively enumerable languages. Here there are no restrictions for the productions. They are many phase structure grammar available for all formal grammars.
Usually they generate the languages that are recognized by a Turing machine.
Let’s assume that all the productions must be in the form of α → β where α is a string of terminals and non-terminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.
Automata Theory Tutorial
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.