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

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

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 <kpreid@mac.com> 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.

> 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.

-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.