What is Grammar
Grammar is a finite set of rules for generating syntactically correct sentences or meaningful correct sentences. These rules are called Productions.
Each production rule is composed of two elements one is Variables and the other is Terminals.
- Variables are the symbols that are used to generate the sentences, but not the part of the sentences. Variables are represented by capital letters. Variables are also known as Non-Terminals.
- Terminals are the symbols that are the components of the sentences generated by the given grammar. Terminals are represented by small letters.
- Productions are the rules of Grammar that specify the substitution of variables. Productions are in the form of $\alpha \to \beta $.
where $\alpha $ is a Non-Terminal and $\beta $ is a Terminal
Formal definition of Grammar
Generally, Grammar G is represented by four tuples. G = (V, T, P, S)
Example:
Consider a Grammar G = (V, T, P, S) |
Types Of Grammar
According to Chomsky, there are four types of Grammar.
Type-0 Grammar
All the productions are in the form of $\alpha \to \beta $
Where, $\alpha \in {\left(V+T\right)}^{+}$
$\beta \in {\left(V+T\right)}^{*}$
Epsilon is not allowed in $\alpha $
Type-1 Grammar
All the productions are in the form of $\alpha \to \beta $
Where, $\alpha \in {\left(V+T\right)}^{+}$
$\beta \in {\left(V+T\right)}^{+}$
and $\left|\alpha \left|\le \right|\beta \right|$
Epsilon is allowed neither in $\alpha $ nor in $\beta $ and length of $\alpha $ must be less than or equal to $\beta $
Type-2 Grammar
All the productions are in the form of $\alpha \to \beta $
Where, $\alpha \in V$
$\beta \in {\left(V+T\right)}^{*}$
and $\left|\alpha \right|=1$
Length of $\alpha $ must be 1.
Type-3 Grammar
All the productions are in the form of $\alpha \to \beta $
Where, $\alpha \in V$
$\beta \in V{T}^{*}or{T}^{*}(LeftLinearGrammar)$
$\in T*or{T}^{*}V(RightLinearGrammar)$
and $\left|\alpha \right|=1$
Length of $\alpha $ must be 1. A grammar can only be Left Linear Grammar or Right Linear Grammar. Any type-3 grammar cannot be both LLG and RLG.
Note: Chomsky Hierarchy only works for grammar with no null production.