# Difference between Type 0 and Type 1 in the Chomsky hierarchy

i am the beginner in linguistics and i have little problem with understanding Chomsky hierarchy. So i have grammar like this:

P = {K -> KL,aK->abK,...}

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. So

K-> KL -- this can be first class aK -> abK -- this isn't first class because if K is transformed to K then a must be transformed to ab which is not true. \alpha X \beta -> \alpha \gamma \beta - is that right?

aXb -> cdb

Is it of Type 0 or Type 1?

EDIT:

a) Type 3

S -> aA A -> baA | aA | ba |

b) Type 3

S -> aS | bs | aA A -> aB | bB B -> \epsilon

c) E -> E + E | E * E | (E) | 2 (what is it and is that unambiguous?)

f) Type 0 because S is on the left side and S -> \epsilon

S -> Sa | Sb | \epsilon

g) Again type 0

S -> SS | (S) | \epsilon

EDIT:

h) aB -> Ba

So if i look on rule of type 1, there is

\alpha X \beta = \alpha \gamma \beta

let say that alpha correspond to 'a' and X should correspond do B. So the rule is not true on the right side? Or is order irrelevant ?

• It's confusing to refer to 1st and 2nd types. The 2nd and 3rd types are Type 1 and Type 2. Your example rule aK->abK is in a Type 1 context sensitive, or Type 0 grammar, since it could be expressed as K->bK /a__. It is not context free (Type 2). Nov 15 '16 at 21:29
• What about something like this aX -> cd is this zero type? What if on the left side is starting symbol? Is there somekind rule of starting symbol on left side in every class? Is grammar can be third type if it looks like this S->ab where S is starting? Nov 15 '16 at 21:32
• Yes, aX -> cd could only be in a Type 0 grammar. Which symbols are start symbols has no bearing on the Type classification. Any finite set of non-terminals can be designated as start symbols for any of the types. Nov 15 '16 at 21:38
• @Hadson Also keep in mind that L3 ⊂ L2 ⊂ L1 ⊂ L0, so everything which is a T3 language is also of T2, everything which is of T2 is also of T1, and all T1 langauges are T0 languages. (But not vice versa.) Nov 15 '16 at 22:19
• I am not sure whether this is a linguistic question or rather a question about theoretical computer science. Chomskys formal languages have nothing in common with natural languages spoken by humans. Nov 16 '16 at 0:04

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.

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.

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.

• OO thank you very much, you are awesome. If you have a moment i added to question few example which i found on the internet. Can you look on them and tell if i determined a type right? Nov 15 '16 at 21:56
• @Hadson Updated. Nov 15 '16 at 22:09