From nobody@digitalkingdom.org Mon Feb 09 15:39:54 2009 Received: with ECARTIS (v1.0.0; list lojban-list); Mon, 09 Feb 2009 15:39:54 -0800 (PST) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1LWfjG-0005ki-9m for lojban-list-real@lojban.org; Mon, 09 Feb 2009 15:39:54 -0800 Received: from mail-qy0-f20.google.com ([209.85.221.20]) by chain.digitalkingdom.org with esmtp (Exim 4.69) (envelope-from ) id 1LWfjC-0005kC-FF for lojban-list@lojban.org; Mon, 09 Feb 2009 15:39:54 -0800 Received: by qyk13 with SMTP id 13so3999541qyk.10 for ; Mon, 09 Feb 2009 15:39:38 -0800 (PST) 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= MIME-Version: 1.0 Received: by 10.229.82.79 with SMTP id a15mr1701933qcl.57.1234222311737; Mon, 09 Feb 2009 15:31:51 -0800 (PST) In-Reply-To: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com> References: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com> Date: Mon, 9 Feb 2009 20:31:51 -0300 Message-ID: <925d17560902091531k16bf93efk7113996d5f786767@mail.gmail.com> Subject: [lojban] Re: CFG prize challenge question From: =?ISO-8859-1?Q?Jorge_Llamb=EDas?= To: lojban-list@lojban.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 15275 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: jjllambias@gmail.com Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list On Sun, Feb 8, 2009 at 6:36 PM, Chris Capel 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.