Re: [lojban] Regular Language

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

On Sat, Sep 03, 2011 at 12:42:25PM -0700, Graham Morehead wrote:
> I'm a computer scientist and amateur linguist.  I just discovered
> Lojban and I'm curious about something:
> 
> Why is lojban a Regular language (in the Chomsky hierarchy), as
> opposed to Context-Free

For the rest of you:
http://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy

We actually don't know where Lojban fits in that hierachy, but it is
certainly *NOT* a regular language.  It probably isn't even context
free.  See
http://groups.google.com/group/lojban/browse_frm/thread/41718340b752ff70
and most of
http://groups.google.com/group/lojban/search?group=lojban&q=cfg&qt_g=Search+this+group

We actually have a $500 prize outstanding for anyone who can produce
a tractable CFG for Lojban.  The issue is elidable terminators,
which are tricky.

Certain parts of Lojban are known to be context sensitive, in
particular ZOI handling, and nothing less than a CSG will do.

The current compromise is to encode Lojban as a
http://en.wikipedia.org/wiki/Parsing_expression_grammar , which is
at least somewhat formal but is not in the chomksy hierarchy at all.

Note that *regular* languages are extremely restrictive; "some
number of "a"s followed by the same number of "b"s" is not a regular
language, for example.  This makes them basically useless for
anything other than extremely simple string matching (i.e. regular
expressions).

> (like all other human languages).  

Wait, what?  No.  No human language is context free, they are all
context sensitive in the chomsky hieararchy, if not actually
unrestricted.  See
http://en.wikipedia.org/wiki/Context-free_grammar#Linguistic_applications
for some citations on that issue.

I'm wondering if you didn't mean CFG when you said regular language
and CSG when you said CFG?

> Isn't it possible to construct a context free generative grammar
> free of ambiguity?

Certainly, but it's not, as far as we know, possible to encode
Lojban in a CFG.

> Once Lojban has enough speakers, and it's set free, it's bound to
> become a context-free language anyway.

We have no particular intention of setting it free at this point;
that was the plan back in the day, but the community has stated
pretty clearly that they'd prefer we stay prescriptivist; see
http://groups.google.com/group/lojban/browse_frm/thread/d8aa194ccc2b5a25
and related discussions.

And, again, you mean "context sensitive" there.

-Robin

-- 
http://singinst.org/ :  Our last, best hope for a fantastic future.
Lojban (http://www.lojban.org/): The language in which "this parrot
is dead" is "ti poi spitaki cu morsi", but "this sentence is false"
is "na nei".   My personal page: http://www.digitalkingdom.org/rlp/

-- 
You received this message because you are subscribed to the Google Groups "lojban" group.
To post to this group, send email to lojban@googlegroups.com.
To unsubscribe from this group, send email to lojban+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/lojban?hl=en.