chomsky hierarchy in plain english

Asked 6/12, 2011 at 9:57 Answered 6/7, 2014 at 2:39

Solved grammar context-free-grammar regular-language context-sensitive-grammar

I'm trying to find a plain (i.e. non-formal) explanation of the 4 levels of formal grammars (unrestricted, context-sensitive, context-free, regular) as set out by Chomsky.

It's been an age since I studied formal grammars, and the various definitions are now confusing for me to visualize. To be clear, I'm not looking for the formal definitions you'll find everywhere (e.g. here and here -- I can google as well as anyone else), or really even formal definitions of any sort. Instead, what I was hoping to find was clean and simple explanations that don't sacrifice clarity for the sake of completeness.

Russel answered 6/12, 2011 at 9:57 Comment(2)

Great question. It should be in every theoretical cs book. – Scandura 6/12, 2011 at 10:37

@muistooshort I'm not sure that it's more suitable for cstheory. It would probably be somewhat appropriate there, but it certainly fits here under the "practical, answerable problems that are unique to the programming profession" banner. In fact, this question is more weighted toward the "practical" side of the scale and less toward the "theory" side as far as grammar classifications are concerned. What I'm asking, specifically, is what the classifications mean in practical terms rather than in purely cs-theory terms. – Russel 7/12, 2011 at 0:5

Maybe you get a better understanding if you remember the automata generating these languages.

Regular languages are generated by regular automata. They have only have a finit knowledge of the past (their compute memory has limits) so everytime you have a language with suffixes depending on prefixes (palindrome language) this can not be done with regular languages.

Context-free languages are generated by nondeterministic pushdown automata. They have a kind of knowledge of the past (the stack, which is not limited in contrast to regular automata) but a stack can only be viewed from top so you don't have complete knowledge of the past.

Context-sensitive languages are generated by linear-bound non-deterministic turing machines. They know the past and can deal with different contexts because they are non-deterministic and can access all the past at every time.

Unrestricted languages are generated by Turing machines. According to the Church-Turing-Thesis turing machines are able to calculate everything you can imagine (which means everything decidable).

Scandura answered 6/12, 2011 at 10:13 Comment(2)

Finite automata can remember information from the past - only a finite amount of it. Your explanation of context-free languages is not correct. The correct class of automata for CFLs is the class of nondeterministic pushdown automata (NPDA). Deterministic pushdown automata are strictly weaker than NPDA. "Context-sensitive languages are generated by non-deterministic pushdown automata." is not correct either. NPDAs generate only CFLs – Rid 6/12, 2011 at 14:13

The terms "Unrestricted languages" and "decidable" in the last item are wrong, because the languages generated by Turing machines (resp. Chomsky Type 0 grammars) are the recursively enumerable languages (the class of recursively enumerable languages sits properly in the class of all formal languages (without any restriction), and the decidable languages sit properly in the recursively enumerable ones). – Hindu 7/3, 2019 at 14:55

As for regular languages, there are many equivalent characterizations. They give many different ways of looking at regular languages. It is hard to give a "plain English" definition, and if you find it hard to understand any of the characterizations of regular languages, it is unlikely that a "plain English" explanation will help. One thing to note from the definitions and various closure properties is that regular languages embody the notion of "finiteness" somehow. But this is again hard to appreciate without better familiarity with regular languages.

Do you find the notion of a finite automaton to be not simple and clean?

Let me mention some of the many equivalent characterizations (at least for other readers) :

Languages accepted by deterministic finite automata
Languages accepted by nondeterministic finite automata
Languages accepted by alternating finite automata
Languages accepted by two-way deterministic finite automata
Languages generated by left-linear grammars
Languages generated by right-linear grammars
Languages generated by regular expressions.
A union of some equivalence classes of a right-congruence of finite index.
A union of some equivalence classes of a congruence of finite index.
The inverse image under a monoid homomorphism of a subset of a finite monoid.
Languages expressible in monadic second order logic over words.

Rid answered 6/12, 2011 at 15:37 Comment(1)

He said he does not formal definitions and what does he get.... formal definitions. – Scandura 6/12, 2011 at 16:1

Regular: These languages answer yes/no with finite automata

Context free: These languages when given input word ( using state machiene and stack ) we can always answer yes/no if it is member of the language

Context sensitive: As long as production in grammar never shrinks ( α -> β ) we can answer yes/no (using state machiene and chunk of memory that is linear in size with input)

Recursively ennumerable: It can answer yes but in case of no it will go into infinite loop

see this video for full explanation.

Calcar answered 6/7, 2014 at 2:39 Comment(0)

Recommended topics

Hot tags