[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lojban] Re: CFG prize challenge question
- To: lojban-list@lojban.org
- Subject: [lojban] Re: CFG prize challenge question
- From: Jorge Llambías <jjllambias@gmail.com>
- Date: Mon, 9 Feb 2009 20:31:51 -0300
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=rhLHX0qf5vSHY1hKoMbksBtpv/3JKcqT7rxBxcZ2tas=; b=wKZF7xcapbNzOJiHHnU1Ez66plz++10VgqbicCqMSomv5xOnLP8euwcIxNg5ZUXqbC nSOypoxalMvcRXqHKenM2xVG4hyWUbXrDRnRUoIw+zGJfg0HuBLd9Vufq/hLX7nXWw5U IS6suKJAyqZcqREbVq5d3oRzEm1sBqxKlHrWA=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=WvofxlY6dWQuUzYWleg4ZHwdTMDGaSWFkkNxzY9FDE2b/jl3hy+ngzEq0k28IHeJLV Trl5MKNo24bbRf6+msiLI1ABGFdw6RqT/0g04jqBmzEGYohufBgIAmFbsz2N5y7qZOlJ iB7kPekOZ2JZ8FeMMDqSSzjK9NDnN7UZvz5fI=
- In-reply-to: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com>
- References: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com>
- Reply-to: lojban-list@lojban.org
- Sender: lojban-list-bounce@lojban.org
On Sun, Feb 8, 2009 at 6:36 PM, Chris Capel <pdf23ds@gmail.com> wrote:
> I'm currently trying to prove that a CFG can't parse grammars with
> elidable terminators without a blowup in productions.
By "blowup" you mean the number of rules increases exponentially with
the number of terminators, right? I don't think that can be proven in
general for grammars with elidable terminators, you need the kind of
recursiveness that the Lojban grammar has for the exponential blowup
to happen. Trivial counterexample:
text = A1 /T1/ | A2 /T2/ | ... | An /Tn/
That grammar has n rules, with n terminators. If the terminators are
made elidable, we only have an increase to 2n rules.
> I'd like to
> verify that the formalism I'm using is satisfactory to the judges.
I'm not one of the judges, but I'm interested, so I have some questions.
> The set of valid phrases to be parsed, P, is a set of lists of tokens.
First question: Do I understand correctly that a phrase is something
like "KOhA BRODA LE BRODA KU VAU"?
The number of valid (and finite) such phrases with non-elidable
terminators is countably infinite, and so is the number with elidable
terminators. There is no blowup there. It is the number of rules,
things like "sumti = LE selbri KU", which is finite, that probably
blows up.
Or is a phrase something like "LE selbri KU", where "selbri" is one of
its tokens? Is "GI NAI" a phrase? It is not by itself "valid" as in a
valid text to be parsed, but there is a rule "gik = GI NAI".
> There are two types of tokens: start and terminator. Each token is
> paired with a number identifying the type of phrase it starts or
> terminates.
What are the types of phrases? Can you give some examples of tokens,
some examples of phrases, and some examples of types of phrases?
I think I'm confused enough at this point, so I'll wait for the
answers before proceeding. :)
mu'o mi'e xorxes
To unsubscribe from this list, send mail to lojban-list-request@lojban.org
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
you're really stuck, send mail to secretary@lojban.org for help.