Wikipedia: Chomsky hierarchy/Talk

I've added a table to Chomsky hierarchy, and moved some of the information from the bullets to the table. I thought it would be easier to see the relationships at a glance if they were in a table. Feel free to resurrect the old bullets (below) if you think that's more readable. -LC

I've reinserted the old description because I feel it is more understandable and gives more explanation for people who don't know the hierarchy already. -- JanHidders

I've fixed the definitions (nonempty γ, Type-1 includes S->&epsilon). I also removed the redundant A->a, for simplicity, and for consistency with some theory books.

I'm curious about the names "Chomsky-n" and "(CHn)". I've always heard people talk of "Type-n" grammars and languages, but not "Chomsky-n" languages. None of my books have it either. A web search turns up lots of hits on "Type-0 grammar" but none on "Chomsky-0". The same is true for the papers archived at [1]. Is this term in widespread use? Or did a textbook coin it for internal use? -LC

I agree with the repair of the Type-1 grammer definition but then you should add a remark at CH1 that the rule S -> ε is also allowed. That way it is indeed the most common form. (I just did some checking in the library.) But for regular grammars the most common form is where all three types of rules are allowed. An important exception is the book by Hopcroft and Ullman Introduction to Automata and Language Theory where they only allow A -> aB and A -> a with the remark that S -> ε is also allowed. Actually I like their approach the best:

type-0 : no restrictions
type-1 : αAβ -> αγβ (with γ <> ε) and maybe S -> ε
type-2 : A -> γ (with γ <> ε) and maybe S -> ε
type-3 : A -> a or A -> aB and maybe S -> ε

Two arguments: (1) the book is a classic, (2) it makes it immediately clear that every higher type grammar is more restrictive than the lower type grammars. The discussion about the alternative definitions and why they are equivalent can always be done in the articles on the specific type of grammer. Deal? :-)

As far as the "Chomsky-n" names are concerned, I didn't introduce those and I also haven't seen them anywhere before. The hierarchy is usually presented as a hierarchy of grammars and not of languages, so I feel we should do the same. -- JanHidders

I agree. These definitions make it clearer that each is a superset of the next. That's nice. I'll go ahead and change the table to use those definitions. The "maybe S->ε" part can go in a sentence after the table, since it also needs to explain that if you use that form, you can't have S on the right side for Type-1.

I changed it from a hierarchy of languages to a hierarchy of grammars, and got rid of the "Chomsky-n" and "CHn" names before, but it slipped back in when the bullets were re-expanded. I'll make that change again. -LC

Useful links for further work