From nobody@digitalkingdom.org Mon Feb 09 16:42:16 2009 Received: with ECARTIS (v1.0.0; list lojban-list); Mon, 09 Feb 2009 16:42:16 -0800 (PST) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1LWghb-0001hM-RN for lojban-list-real@lojban.org; Mon, 09 Feb 2009 16:42:16 -0800 Received: from yx-out-1718.google.com ([74.125.44.152]) by chain.digitalkingdom.org with esmtp (Exim 4.69) (envelope-from ) id 1LWghY-0001h8-Rv for lojban-list@lojban.org; Mon, 09 Feb 2009 16:42:15 -0800 Received: by yx-out-1718.google.com with SMTP id 3so134222yxi.46 for ; Mon, 09 Feb 2009 16:42:11 -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=wnTKcrXNlM4mTUu6L97fD1fz+B6KqDM1ROiXImQeNvg=; b=LIM8jgqKavlMNpuWIUMlRl/GUodPdtp9ke7p1VwpRxFLmS4AT31zki42qy7gvrbMvH KVzHL/qIa2IxqbmStOPcjMdwA0GteFiD0sv1ljzYDGGv9Vwd0ydtNulNZabYGQXVpslN TdEF5JMT7GZWe/u0jIXBMgkBJDIjdvCi2tsCs= 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=i2ju2x1rg8mVumrEpwoo/cOxS2HpdBFS0/AMaFGxzeUYIgc5hCRdijQYtr5Wa+DpWQ 08KW2uwGSugyrD5zbs0EaGV2C5LXZxn0cKQ0pe41bnqFGoSalusmUYOF0MNmKnE8K161 vDGilerKH6WUJ6eQU+kFbD//v/Rh9M4OtFzUc= MIME-Version: 1.0 Received: by 10.151.114.9 with SMTP id r9mr3393982ybm.73.1234226531719; Mon, 09 Feb 2009 16:42:11 -0800 (PST) In-Reply-To: <925d17560902091531k16bf93efk7113996d5f786767@mail.gmail.com> References: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com> <925d17560902091531k16bf93efk7113996d5f786767@mail.gmail.com> Date: Mon, 9 Feb 2009 18:42:11 -0600 Message-ID: <737b61f30902091642h7e41234ufc1bdd8e7ddb5f6c@mail.gmail.com> Subject: [lojban] Re: CFG prize challenge question From: Chris Capel To: lojban-list@lojban.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by Ecartis X-Spam-Score: -0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 15279 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: pdf23ds@gmail.com Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list On Mon, Feb 9, 2009 at 17:31, Jorge Llambías wrote: > 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? Well, more like with the number of allowable parent-child phrase relationships. E.g., you can nest a sumti in a selbri, so that's one. You can put a selbri in a bridi, so that's two. You can put a TO-TOI in lots of places, so that's like ten more. Etc. And I don't assert that the blowup is exponential--I'd sooner believe it's polynomial. But either way I'm really not to sure how to go about *proving* it. >> 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"? Well, I'm thinking more abstractly. I don't think KOhA has a terminator, so I'm just assuming that kind of word is irrelevant. And I'm representing all terminators, so I think you'd need "BRODA LE BRODA VAU KU VAU". But that's basically it. > 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. That's the idea. > Or is a phrase something like "LE selbri KU", where "selbri" is one of > its tokens? A selbri has internal structure, including some terminators (I believe) so it would be represented as various phrase types. > 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". I don't think NAI is really a terminator, so "GI NAI" wouldn't be represented in my formalism. >> 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? The concrete syntax I've been using is as follows: "(x" is a start token of type x, ")x" is a terminator token, non-elided, and "_)x" is an elided terminator. So an example phrase would be (1 (2 (3 (4 )4 _)3 _)2 (3 )3 )1 This phrase is invalid, because of the second 3 phrase. Since the 2 terminator is elided, the second 3 phrase would have to be grouped under the 2 phrase after the first 3 phrase. In other words, if you removed the elided terminators and reconstructed them, the 2 terminator would go after the second 3 phrase. I think you can see how a unique number could be assigned to each selma'o that starts a terminable phrase, and the allowed nestings declared as assumptions about the mapPhPh function, to make a mapping between lojban and the formalism. Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet) 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.