W3C home > Mailing lists > Public > public-ixml@w3.org > August 2021

an infinitely ambiguous language

From: C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com>
Date: Tue, 17 Aug 2021 12:31:18 -0600
Message-Id: <79906049-4CEA-4A81-A022-CDC899ECD41C@blackmesatech.com>
Cc: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>
To: public-ixml@w3.org
I promised I would give an example of a sentence which is
infinitely ambiguous — by which I mean a sentence with an 
infinite number of parse trees.  Here it is:

     S : ‘a’; S.

Trees include <S>a</S>,  <S><S>a</S></S>, <S><S><S>a</S></S></S>, etc.

Here is another:

    S: P+, ‘a’, Q+.
    P: .
    Q: .

The first grammar is ‘vertically’ ambiguous:  arbitrary depth of nesting.
The second is ‘horizontally’ ambiguous:  arbitrary numbers of empty

C. M. Sperberg-McQueen
Black Mesa Technologies LLC
Received on Tuesday, 17 August 2021 18:31:38 UTC

This archive was generated by hypermail 2.4.0 : Tuesday, 17 August 2021 18:31:40 UTC