From nobody@digitalkingdom.org Thu Oct 30 12:26:43 2008 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 30 Oct 2008 12:26:43 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1KvdAJ-0006gN-4E for lojban-list-real@lojban.org; Thu, 30 Oct 2008 12:26:43 -0700 Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1KvdAJ-0006gG-2E for lojban-list@lojban.org; Thu, 30 Oct 2008 12:26:43 -0700 Date: Thu, 30 Oct 2008 12:26:43 -0700 From: Robin Lee Powell To: lojban-list@lojban.org Subject: [lojban] Re: [lojban-beginners] A challenge for computer science/programming geeks: The LLG wants to give you $500! Message-ID: <20081030192643.GV1092@digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <20081028215134.GK31434@digitalkingdom.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.18 (2008-05-17) X-archive-position: 14888 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: rlpowell@digitalkingdom.org Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list On Thu, Oct 30, 2008 at 11:21:45AM -0800, Stephen Pollei wrote: > On 10/28/08, Robin Lee Powell wrote: > > > > 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 $100: Formally prove that encoding Lojban's elidable > > terminators is not possible in a CFG. > > I've been thinking about the problem as well as I think the issue > is the ambiguity. For instance I beleive that any peg grammar can > be reduced into a most likely weaker cfg grammar that has > potentialy multiple parse trees for the same valid statement in > the grammar. You're wrong, I'm afraid. http://en.wikipedia.org/wiki/Parsing_expression_grammar#Examples Look for "The following parsing expression grammar describes the classic non-context-free language". PEGs can encode things that CFGs simply cannot, ambiguously or otherwise. This is why Lojban's status is an interesting open question: we can do elidable terminators in PEG, but haven't been able to in CFGs. -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/ 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.