Changes

as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult. The following table provides a summary, which is then explained further in the subsequent subsections.

as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult. The following table provides a summary, which is then explained further in the subsequent subsections.

In the late 1950's, [[John Backus]] and Peter Naur independently developed a notation for describing [[programming language]]s (specifically for Algol 60 in fact). This notation is known as Backus Naur Form (or BNF) and turns out to be equivalent to Chomsky's grammar number two (context-free grammar).

In the late 1950's, [[John Backus]] and Peter Naur independently developed a notation for describing [[programming language]]s. This notation was first used in the defining Algol 60 Report, and has since been used for specifying other programming languages. This notation is known as Backus Naur Form (or BNF) and turns out to be equivalent to Chomsky's grammar number two (context-free grammar).

{| class="wikitable"

{| class="wikitable"