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

["Jorge Llambías" <jjllambias@gmail.com>]

On Wed, Oct 29, 2008 at 3:19 PM, Robin Lee Powell
<rlpowell@digitalkingdom.org> 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 <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.

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.