Re: Universal grammar

On Wed, 18 Oct 2006, Hans Aberg wrote:

The "Chomsky hierarchy" shows up as a classification of formal
mathematical grammars.

One should not overestimate the significance of that hierarchy, not even
for formal languages (of which I understand more than of natural
languages). Chomsky type 0 grammars are undecidable which limits their
usefulness, type 1 grammars (CS) are so large a subset of decidable
languages that more or less any decidable language of practical use may be
CS but with no sensible way to construct a CS grammar or to understand
what language a CS grammar will produce. Only type 2 languages (CF) have
two nice properties:

- If the language they describe happen to have a parenthesis structure
as is typical for CF languages, then a CF grammar reflecting this
structure is easy to read. This is why they are used to define
programming languages, and may be used to describe some aspects of
natural languages.

- For a small subset of them, nice parsing algorithms have been found.
This subset comprises the programming languages, if only because these
were defined in a way that this works (FORTRAN, the oldest of these, is
not deterministic, though).

Taking the Chomsky hierarchy as a measure for complexity is, however,
questionable (see my posting <70n9i7$j6h$1@xxxxxxxxxxxxxxxxxxxxxxxxxxx>).

The more general formal grammars are though
in practice not used so much in favor of so called context free grammars
(CFG) combined with context dependencies implemented using semantic
actions attached to the grammar rules.

In other words, these languages are *not* context free so that some
syntactic rules are disguised as "semantic". As an engineering approach,
this is in order (use CF for what they are good for, to wit the two items
above, and use something else for the rest) but it stresses that CF
grammars do not reflect the *entire* syntactic structure underlying the
language - be it an artificial or a natural one.

--
Helmut Richter
.

Relevant Pages

  • Re: Election 2008 for computer programmers
    ... associated with the most expressive grammars. ... their languages are recognised by finite state automata. ... infantilization of politics, and part of that infantilization is your ... Chomsky numbers changes the fact that the very ability to either read ...
    (comp.programming)
  • Re: Wackernagel Position
    ... Though it's rare that there's anything significant about Australian languages -- I'm the only one here who has a particular interest in them. ... Let me answer a few of the comments about my Pama-Nyungan subgrouping ... languages with wordlists but no grammars. ... (In Ringe's IE, ISTM some of his features are "lumped", others not.) ...
    (sci.lang)
  • Re: Extended context-free grammar
    ... of the operators commonly used to write grammars), ... and I cannot see any better way of defining it: ... In the partial order of languages ordered by inclusion, ... of languages is equality of languages, so adjunctions are a good way ...
    (comp.theory)
  • Re: Visitor, dynamic_cast or ...
    ... we invent new grammars to deal with it. ... are the harbingers of the next languages. ... syntax, and a good polymorphic creation syntax, and a good reflection ... Object Mentor Inc. | unclebob @ objectmentor. ...
    (comp.object)
  • Re: Hardest to learn between Russian and Irish
    ... > Tolomako made do with so little. ... > what the Tolomako-speaking villagers meant ... The anecdotes would be credible if the resulting published grammars of ... closely related languages -- if, for example, as happened with Hockett's ...
    (sci.lang)