DHARM278 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEl A production of type bABc → babbc is certainly a valid production. On left side it
contains 2 non terminals and the length of derived symbols (5) is greater than length
of derivatives symbols (4).
l Aab → ε is not a valid production. Because, | Aab| ≤/ | ε | or length of derived symbol
(0) is not greater than or equal to the length of derivatives symbols (3).
The grammars follow restriction 2 along with restrictions 1 is called ‘Context Sensitive
Grammar’ or ‘Type-1 Grammar’ or ‘Length Increasing Grammar’ and its language is called
‘Context Sensitive Language’ or ‘Type-1 Language’ or ‘Length Increasing Language’.
III. Restriction 3 (followed Restriction 2 + Restriction 1)
If the grammar G has the production α → β then besides, restriction 1 & restriction 2,
there is another restriction i.e.,
α must be a single non terminal symbol
Examples of the valid productions are,
l A → ab; there is only a single derivative symbol that is A, and restriction 1 and 2 also
fulfill.
l B → aABc
l A → ε is also a valid production.
So the grammar that is bounded under these restrictions (1, 2 and 3) is ‘Context Free
Grammar’ or ‘Type-2 Grammar’ and so the language is ‘Context Free Language’ or ‘Type-
2 Language’.
The automaton accepts such type of language is Push down Automata.
IV. Restriction 4 (followed Restriction 3 + Restriction 2 + Restriction 1)
In the grammar G, if α → β is a production then, besides above restrictions (1, 2, 3)
restriction 4 says, β must be a single terminal symbol or a terminal followed by a
nonterminal symbol.
Such as, followings are the valid type productions:
l A → b; where b ∈ VT.
l A → bC; a terminal symbol b is followed by symbol C ∈ VN.
The grammar fulfill above restrictions (1,2,3,4) is ‘Regular Grammar’ or ‘Type-3 Gram-
mar’ and the language generated by G is ‘Regular Language’ or ‘Type-3 Language’.
As we say earlier if grammar G = (VT, VN, S, P) then language generated by grammar G
is L (G) where,
L (G) = {x ∈ VT*/S ⇒N x}
From starting symbol S and by using the production/s (∈ P) we reaches to the string x
(that is formed over set of terminal symbol/s) in finite steps.
Note. At any stage of productions propagation if, α 1 A α 2 ⇒α 1 γ α 2 then surely, A → γ is a
production where α 1 and α 2 ∈ (VT ∪ VN)*