Quick recap*:
where greek letters denote a (possibly empty) sequence of terminal and non-terminal symbols, capital roman letters denote non-terminal symbols and lower case roman letters denote terminal symbols.
* Just noticed that there is an error in the last row of the table; the rule type A -> a or A -> ϵ is missing.
Type 0 grammars are completely unrestricted, whereas Type 1 grammars require all production rules to contain at least one non-terminal on the left-hand side (= LHS) of the rule which then expands to whatever sequence of non-terminal and terminal symbols on the right-hand side (= RHS), i.e. the LHS can not contain only terminal symbols. Type 2 allows only one non-terminal on the LHS; Type 3 additionally prohibits sequences other than one non-terminal and one terminal, or just one terminal on the RHS.
So let's take a look at your example:
K -> KL
aK -> abK
...
- All of such phrase structure grammars are of type 0, so that part is
clear.
- Now as for the question of whether it is also of type 1, you
have to check whether the requirement is met that there is at least
one non-terminal symbol on the LHS of the rule. This is the case for
all the rules you listed (one rule has
K, the other rule has aK), and in case your grammar doesn't contain
other production rules which possibly do not match this format, you
can say that the grammar is indeed context-sensitive.
- Next for Type 2. This would mean that all LHSs need to consist of only one non-terminal symbol. But clearly, this requirement is violated: Since the rule
aK -> abK has a as a part of its LHS, the condition for context-freenes is not met. The grammar is thus not of type 2, and hence also not of type 3, as you correctly predicted.
As for your suggestion:
In my opinion, it is not third or second class because on the left side of -> there is something more than one non-terminal. It can first or zero class.
Yes, this is correct, as explained in the previous paragraph.
K-> KL -- this can be first class
Yes. There is a non-terminal (K) on the LHS which transforms to some sequence of non-terminals (KL) on the RHS, so it matches the rule format for Type 1 grammars.
abK -- this isn't first class because if K is transformed to K then a must be transformed to ab which is not true
This is not correct. Type 1 means that the LHS must contain one non-terminal symbol which on the RHS corresponds to some sequence of terminal or non-terminal symbols, \gamma, and this requirement is met by K being part of the left-hand side. That aK eventually tranforms to abK (because \alpha and \beta respectively denote the same string on both sides of the rule) is completely okay.
\alpha X \beta -> \alpha \gamma \beta Is that right?
Yes, this is right, but I think you misinterpreted this rule. Applied to your example, \alpha is a, X is K and \beta is empty. On the RHS, \alpha needs to be the same as the \alpha on the left-hand-side, that is, a, \beta is again empty, and now \gamma is the sequence bK. This is okay; as \gamma can be any sequence of terminal or non-terminal symbols, it is okay for K to go to aK.
Next to your final example:
aXb -> cdb
- Any rule of the form
\alpha -> \beta belongs to a grammar of Type 0, so this one does too.
- In order to also be of Type 1, you need to ensure that the LHS contains a non-terminal which then expands to whatever sequence of non-terminals and terminals on the RHS.
This requirement is not met, since, although you have a non-terminal (K) on the LHS, the \alpha left to the non-terminal X which is a disappears on the right, but \alpha on the LHS and \alpha on the RHS must denote the same string (which a and the empty string don't), so independently of what Xb expands to, the rule doesn't fit the format of a Type 1 grammar. A grammar with such a production rule is thus only of Type 0 and nothing else.
a) Type 3
S -> aA A -> baA | aA | ba |
The rule A -> baA is not allowed in T3 grammars because you have one terminal too much on the right (it should only be one terminal + one non-terminal, or only one terminal), so this is not T3, only T2.
b) Type 3
S -> aS | bs | aA A -> aB | bB B -> \epsilon
Same here; with S -> bs you have two terminals on the RHS, this is ruled out by T3, so this grammar is only T2.
c) E -> E + E | E * E | (E) | 2 (what is it and is that unambiguous?)
I don't know what the symbols are intended to mean, but I could imagine this is a grammar describing algebraic terms (like 1+2, (3*4)+6 and so on). With a mixture of terminals and non-terminals on the RHS, but only one non-terminal on the LHS, this would be T2.
f) Type 0 because S is on the left side and S -> \epsilon
S -> Sa | Sb | \epsilon
Yes
g) Again type 0
S -> SS | (S) | \epsilon
Yes.
