SkipCaptcha
265
edits
Changes
→Chomsky hierarchy: note re Backus Naur Form
}}</ref>
}}</ref>
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).
{| class="wikitable"
{| class="wikitable"