[lojban] Re: [llg-members] 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 11:34:37AM +0300, Cyril Slobin wrote:
> On 10/29/08, Robin Lee Powell <rlpowell@digitalkingdom.org> wrote:
> 
> >  > A machine that generated its output from such a grammar would
> >  > generate valid Lojban. If you want an unambiguous CFG (which
> >  > is obviously a somewhat harder problem) I think you need to
> >  > specify it.
> >
> >  Then please, everyone, consider it so specified.  Apologies for
> >  triple posting again, but if xorxes is right this is important.
> 
> Correct me if I mislook something, but without this clarification
> the task seems to be trivial, isn't it? If we don't care about
> parsing tree, we can just make all elidable terminators optional
> and get the solution. Look at a very tiny subset of the language:
> 
> <bridi> ::= broda | <bridi> <bridi> | nu <bridi> | nu <bridi> kei
> 
> The string "nu broda broda" can be generated in two ways:
> 
> ((nu broda) broda) and (nu (broda broda))
> 
> , but the grammar generates all good strings and only good strings.
> Therefore unambiguity is the central difficulty there.

Fair warning: it's been a *long* time since I worked on this.

Your example is too simple to show the problem.

sentence ::= <sumti> <selbri> | <sumti> <selbri> <sumti>
sumti ::= le <selbri> ku | le <selbri>
selbri ::= <brivla> | <brivla> <selbri>
brivla ::= klama

This will generate the *incorrect* sentence "le klama klama".
That's a valid utterance, but it's *not* a Lojban sentence, and
a parser based on this grammar will mark it as such.

The definition of an elidable terminator is that it can be dropped
when no ambiguity (or significant change to the parse tree) results.
In this case, the ku is not elidable, but it is not obvious how to
make a CFG that refuses "le klama klama" but accepts "le klama ku
klama le klama"

If you think you've found a way, try adding another elidable
terminator that interacts directly with ku.

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