[lojban] Re: [lojban-beginners] A challenge for computer science/programming geeks: The LLG wants to give you $500!

[Robin Lee Powell <rlpowell@digitalkingdom.org>]

On Thu, Oct 30, 2008 at 11:21:45AM -0800, Stephen Pollei wrote:
> On 10/28/08, Robin Lee Powell <rlpowell@digitalkingdom.org> 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.