From nobody@digitalkingdom.org Wed Oct 29 11:40:26 2008 Received: with ECARTIS (v1.0.0; list lojban-list); Wed, 29 Oct 2008 11:40:27 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1KvFxy-0005VO-QY for lojban-list-real@lojban.org; Wed, 29 Oct 2008 11:40:26 -0700 Received: from rv-out-0708.google.com ([209.85.198.248]) by chain.digitalkingdom.org with esmtp (Exim 4.69) (envelope-from ) id 1KvFxv-0005V0-MC for lojban-list@lojban.org; Wed, 29 Oct 2008 11:40:26 -0700 Received: by rv-out-0708.google.com with SMTP id b17so130106rvf.46 for ; Wed, 29 Oct 2008 11:40:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=NdYwDlF9B9QNO4/bo8po7QUwAO8M0wJx5H1GD4ScLh0=; b=H1MCy2VHGCasQx4hVB5GIYvDuI/uD3XW8aT0aLLsCA2avVtmlW8mpG5ha8qacIr0Gn GRArQtRAOa5bwhm/2xqyyo6vPY2obEeuohTkQsFjgIdD1qQhHDPujSx8IkABUY0KIXYR 42WB7wadT1PEAL07vmYYEjaHNuZECkvsdmEvY= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=Skz2M4WLDVdCPmrVGpCcXqu0Cm7w6Z90+VlSO17u/wlVhn8/1BS8FF0WF2JW+37/dC gQL6rNDh2wjf6/lDcGH9xhsemd1vx7Lo70TKFXTULvj4sYMXzTJ/yxipfXOAXPN2psCo hDb0KT4SZiyH7B57YnywQ+MHLUrnb4xVV13oA= Received: by 10.141.106.14 with SMTP id i14mr5086442rvm.178.1225305622745; Wed, 29 Oct 2008 11:40:22 -0700 (PDT) Received: by 10.141.194.15 with HTTP; Wed, 29 Oct 2008 11:40:22 -0700 (PDT) Message-ID: <925d17560810291140tc8f35e4xe01d8000615190e2@mail.gmail.com> Date: Wed, 29 Oct 2008 15:40:22 -0300 From: "=?ISO-8859-1?Q?Jorge_Llamb=EDas?=" To: lojban-list@lojban.org Subject: [lojban] Re: [llg-members] Re: Re: A challenge for computer science/programming geeks: The LLG wants to give you $500! In-Reply-To: <20081029181912.GE26657@digitalkingdom.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by Ecartis Content-Disposition: inline References: <20081028215134.GK31434@digitalkingdom.org> <925d17560810281730t6ab2f3c3i860e7b086de5aa4c@mail.gmail.com> <20081029005927.GH26657@digitalkingdom.org> <925d17560810281820m5bf3844ey27fd29da6e44a716@mail.gmail.com> <20081029012419.GM26657@digitalkingdom.org> <925d17560810281830h2b491a81s5b128a59561963c1@mail.gmail.com> <20081029013224.GO26657@digitalkingdom.org> <44620A63-76DB-4D3A-BAB7-0A8E6D4AEAFC@mac.com> <925d17560810290541g1c257444t6e214ccc54ccd17c@mail.gmail.com> <20081029181912.GE26657@digitalkingdom.org> X-Spam-Score: 0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 14882 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 Wed, Oct 29, 2008 at 3:19 PM, Robin Lee Powell wrote: > On Wed, Oct 29, 2008 at 09:41:57AM -0300, Jorge Llambías wrote: >> On Wed, Oct 29, 2008 at 7:27 AM, Kevin Reid wrote: >> > >> > An unambiguous grammar for the same set of parse trees would be >> > >> > SELBRI -> SBATOM | SELBRI SBATOM >> > SBATOM -> BRIVLA | "ke" SELBRI "ke'e" >> >> And to make "ke'e" elidable: >> >> SELBRI -> SELBRI-closed | SELBRI-open >> SELBRI-closed -> SBATOM-closed | SELBRI-closed SBATOM-closed >> SELBRI-open -> SBATOM-open | SELBRI-closed SBATOM-open >> SBATOM-closed -> BRIVLA | "ke" SELBRI "ke'e" >> SBATOM-open -> "ke" SELBRI > > Again, this is too simple to actually illustrate the problem: there > is no sentence that Kevin's example generates that is illegal if > you remove a ke'e. True, but there are sentences that could be ambiguously parsed if ke'e is simply optional. "ke broda brode" would have two valid parses. What I gave is an unambiguous grammar that handles the elidability of "ke'e". Indeed this is too simple to show all the isssues with terminators, but it already shows how the number of rules required increases. (I later thought of a way of doing it with four rules rather than five, but still.) >> My first impresssion is that the mission truly is impossible: i.e. >> it is possible to handle the elidable terminators, but not with >> less than 2000 production rules, because handling each terminator >> will multiply the number of productions by some factor, and there >> are a lot of terminators. But that's just my first impression. > > I don't believe it's possible even with 100K productions; I would be > very interested to be proven wrong on that. But you didn't offer any money for that proof! ;) 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.