DHARMNON-REGULAR GRAMMARS 277Each grammar must start with a symbol which is called start symbol; all other symbols
(terminals/nonterminals) are linked next to start symbol. Throughout the context we denote S
as a start symbol and since it doesn’t part of the language so S ∈ VN. Hence,
l VN ≠ Ø {set of nonterminal symbols must has at least a symbol that is a starting
symbol S}
l VT ∩ VN = Ø {nothing is common between terminal symbols and variables}
In the grammar G productions are defined as,
α → β
It can be read as ‘α derives β’ or ‘left symbol(s) derives right symbol(s)’, where
α, β ∈ (VN ∪ VT)*
11.3CLASSIFICATION OF GRAMMAR - CHOMESKYS HEIRARCHY
Since productions or rules provides the basis to the grammar. A rule may be represented
by α → β. There are several possibilities of the selection of the term α and β in the rule.
On the basis of these selections of α and β we classify the productions. Therefore, there are
several restrictions in the production α → β on which grammars are classified.
I. Restriction 1
α must contain at least one nonterminal
i.e. α ∈ (VN ∪ VT). VN. (VN ∪ VT) and β ∈ (VN ∩ VT)
Let VT = {a, b, c} and VN = {S, A, B, C} then applying this restriction following are only
valid productions,
l aABac → abBC
(Here α (left side of production) is aABac, which contains two nonterminals A and B
and β (right side of production) is abBC and both α and β ∈ (VN ∩ VT).
l But ab → ABab is not a valid production, because on its left side there is not a single
nonterminal symbol.
l If ε ∈ VT then, Aab → ε is a valid rule. [where ∈ is a null string]
l But ε → ab is not a valid production because ε ∈ VN. Therefore, α ≠ ε.
The grammar defined under above restriction is called ‘Phase Structured Grammar’ or
‘Type-0 Grammar’ or ‘Recursive Enumerable Grammar’ and the language generated by this
grammar is called ‘Phase Structured Language’ or ‘Type-0 Language’ or ‘Recursive
Enumerable Language’. The automata accept such language is Turing machine.
II. Restriction 2 (followed by restriction 1)
For the grammar G, if α → β is a rule then along with the restriction I such that α contains at
least a nonterminal it follows another restriction, | β | ≥ | α | ; or length of right side
derived symbols is not less than the length of left side derivatives symbols.
i.e. α ∈ (VN ∪ VT). VN. (VN ∪ VT) and β ∈ (VN ∪ VT)* and also | α | ≤ | β | and β ≠ ε.
l From the previous example of production i.e., aABac → abBC is not a valid production
here, because | abBC | ≥/ | aABac |, on left side there should at least five symbols
(terminals/nonterminals) but it fulfill restriction 1.