From nobody@digitalkingdom.org Wed Oct 29 07:17:13 2008 Received: with ECARTIS (v1.0.0; list lojban-beginners); Wed, 29 Oct 2008 07:17:13 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1KvBrD-0008LH-O1 for lojban-beginners-real@lojban.org; Wed, 29 Oct 2008 07:17:13 -0700 Received: from mailgw3a.lmco.com ([192.35.35.7]) by chain.digitalkingdom.org with esmtp (Exim 4.69) (envelope-from ) id 1KvBr6-0008Kg-86 for lojban-beginners@lojban.org; Wed, 29 Oct 2008 07:17:11 -0700 Received: from emss04g01.ems.lmco.com (relay4.ems.lmco.com [166.17.13.122])by mailgw3a.lmco.com (LM-6) with ESMTP id m9TEH22w003792for ; Wed, 29 Oct 2008 10:17:02 -0400 (EDT) Received: from CONVERSION2-DAEMON.lmco.com by lmco.com (PMDF V6.3-x14 #31428) id <0K9I00I017OEYB@lmco.com> for lojban-beginners@lojban.org; Wed, 29 Oct 2008 10:17:02 -0400 (EDT) Received: from EMSS02I00.us.lmco.com ([166.29.2.48]) by lmco.com (PMDF V6.3-x14 #31428) with ESMTP id <0K9I002L97O3DH@lmco.com> for lojban-beginners@lojban.org; Wed, 29 Oct 2008 10:16:57 -0400 (EDT) Received: from emss02m20.us.lmco.com ([166.29.2.189]) by EMSS02I00.us.lmco.com with Microsoft SMTPSVC(5.0.2195.6713); Wed, 29 Oct 2008 08:16:51 -0600 Date: Wed, 29 Oct 2008 08:15:52 -0600 From: "Rostowfske, Luke J" Subject: [lojban-beginners] Re: A challenge for computer science/programming geeks: The LLG wants to give you $500! In-reply-to: <20081028215134.GK31434@digitalkingdom.org> To: lojban-beginners@lojban.org Message-id: <6E2DF1575F3F2043AC2E1E8E56C5853D0CCAC848@emss02m20.us.lmco.com> MIME-version: 1.0 X-MIMEOLE: Produced By Microsoft Exchange V6.5 Content-Type: text/plain; charset=us-ascii Content-transfer-encoding: 7BIT Thread-Topic: [lojban-beginners] A challenge for computer science/programming geeks: The LLG wants to give you $500! Thread-Index: Ack5R57H+2+AHPthSUCSjYdZCdQ5uQAiOqWw Content-class: urn:content-classes:message X-MS-Has-Attach: X-MS-TNEF-Correlator: References: <20081028215134.GK31434@digitalkingdom.org> X-OriginalArrivalTime: 29 Oct 2008 14:16:51.0724 (UTC) FILETIME=[FCFDC4C0:01C939D0] X-Spam-Score: -8.0 X-Spam-Score-Int: -79 X-Spam-Bar: -------- X-archive-position: 951 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-beginners-bounce@lojban.org Errors-to: lojban-beginners-bounce@lojban.org X-original-sender: luke.j.rostowfske@lmco.com Precedence: bulk Reply-to: lojban-beginners@lojban.org X-list: lojban-beginners I was going to do this anyway, so challenge accepted! Phase 1. Guess I must learn Lojban. Phase 2. ??? Phase 3. Profit! Respectfully, Luke Rostowfske GPS IIR Flight Ops, LMSS -----Original Message----- From: lojban-beginners-bounce@lojban.org [mailto:lojban-beginners-bounce@lojban.org] On Behalf Of Robin Lee Powell Sent: Tuesday, October 28, 2008 3:52 PM To: lojban-list@lojban.org; lojban-beginners@lojban.org; llg-members@lojban.org Subject: [lojban-beginners] A challenge for computer science/programming geeks: The LLG wants to give you $500! Your mission, should you choose to accept it, is to create a CFG for Lojban. There are three options, with different monetary values attached, in order of what we in the LLG board would prefer to get. For $500: Produce a working CFG for Lojban, in any format that some parser generator somewhere can accept, *or* in BNF or a well defined extension thereof. It must support every aspect of the language except for ZOI (which is fully context sensitive). Elidable terminators are the hard part. To stop brute-force solutions that would make the resulting grammar effectively useless, the total number of productions in the CFG language must be less than 2,000. Each alternation counts as a production for this purpose. For comparison, a quick check of the current BNF shows less than 200. *OR* For $300: Produce a CFG that correctly encodes 5 Lojban elidable terminators and all the structures needed to produce sentences using whatever features they terminate, with instructions for how to add more. Two of those must be VAU and KU, which means your sub-language must be able to produce real bridi. The instructions for how to add more must be complete; that is, I should be able to add an elidable terminator and its continget structurs inside of half an hour. You must also demonstrate that the number of productions does not grow much more than linearly; i.e. you must demonstrate that the total number of productions in the resulting CFG will be less than 2,000. Each alternation counts as a production for this purpose. For comparison, a quick check of the current BNF shows less than 200. *OR* For $100: Formally prove that encoding Lojban's elidable terminators is not possible in a CFG. Details: If you produce a grammar, I don't care what parser generator it needs, or even if such a parser generator exists. I care only that the language is actually a CFG, and that a parser generator could, in principle, be built for whatever you came up with. Having said that, I don't think it's formally possible to produce a CFG that (for example) Perl's Parse::RecDescent can't recognize, and the more obscure your CFG is the longer it'll take us to give you the money. No matter what you do, John Cowan and myself will be reviewing it. We are the final arbiters of whether you have met the community's needs, and our vote must be unanimous (this is not a problem: I don't think we've ever disagreed on things of this level of technical detail after we've had a chance to discuss them). You'll probably want to start with the "extended" BNF at http://www.lojban.org/tiki/tiki-index.php?page=Lojban+Formal+Grammars&bl =y It is a nonstandard BNF, in that it has markers for "magic elidable terminators go here". You may want to use http://www.digitalkingdom.org/~rlpowell/hobbies/lojban/grammar/lojban.ab nf.txt instead. In case of confusion, the files above take precedence, and the CLL takes precedence over those, but if you have such confusion, you *MUST* explicitely mark it in your report on the work you've done. Your grammar is permitted to not implement the following things: ZOI (impossible in a CFG) SI/SA/SU BU ZEI The reason is that those are Hard; see http://www.lojban.org/tiki/tiki-index.php?page=Magic+Words&bl=y It must, however, be *possible* to implement all of them except ZOI. Example, simplified implementations of each is therefore encouraged. *********** * WARNING * *********** I and several other people have looked at this problem and strongly believe that it is impossible to encode Lojban elidable terminators in a CFG, at least without an exponential in the number of terminators number of productions. -Robin -- They say: "The first AIs will be built by the military as weapons." And I'm thinking: "Does it even occur to you to try for something other than the default outcome?" -- http://shorl.com/tydruhedufogre http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/