Classifying Grammars
A procedure to classify grammars is below.
1. Check the left hand side of every rule L ¡ú R1 | R2 | …Rn. If there is any rule with |L| > 1, then
the grammar is context-sensitive or unrestricted. Otherwise it is context-free.
2. To distinguish between context-sensitive and unrestricted grammars, do the following.
(a) If every rule L ¡ú R1 | R2 | …Rn is either S ¡ú ¦Ë or such that |L| ¡Ü |Ri| for all 1 ¡Ü i ¡Ü n, then the grammar is context-sensitive.
(b) IfthereisanyruleoftheformA¡ú¦ËwhereAisnotS,oranyruleL¡úR1 |R2 |…Rn with |L| > |Ri| for some 1 ¡Ü i ¡Ü n, then the grammar is unrestricted but not context-sensitive.
3. To distinguish between context-free and regular grammars, do the following.
(a)IfeveryruleL¡úR1 |R2 |…Rn issuchthatforall1¡Üi¡Ün,Ri iseither¦Ë,asingle terminal, or a single terminal followed by a single variable, then the grammar is regular. So every rule must be of the form A ¡ú ¦Ë, A ¡ú a or A ¡ú aB.
(b) IfthereisanyruleL¡úR1 |R2 |…Rn suchthatforsome1¡Üi¡Ün,Ri isnotasingle terminal, or a single terminal followed by a single variable, then the grammar is context-free butnotregular. SothereissomerulewhichisnotoftheformA¡ú¦Ë,A¡úaorA¡úaB.
1