From lojban+bncCK30vq5WEMCQivMEGgTDdTsu@googlegroups.com Sat Sep 03 13:04:27 2011 Received: from mail-pz0-f56.google.com ([209.85.210.56]) by chain.digitalkingdom.org with esmtp (Exim 4.72) (envelope-from ) id 1QzwS0-00017x-CR; Sat, 03 Sep 2011 13:04:27 -0700 Received: by pzk33 with SMTP id 33sf8552731pzk.1 for ; Sat, 03 Sep 2011 13:04:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=beta; h=x-beenthere:received-spf:date:from:to:subject:message-id:references :mime-version:in-reply-to:user-agent:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-google-group-id:list-post:list-help:list-archive:sender :list-subscribe:list-unsubscribe:content-type:content-disposition; bh=eheG2mQ172CcZpTzVLcfuVJXzQ18t6W84hv1wrI4GbI=; b=HvPLH5K8dOlu/Bv4WB2+6WiaB61niF5jBtpO2C4PtrH5ZJr+YpN3PFLr2cYNoF7HDh ANdDzegYxHKa1iAuH1PSMTLKwWkcIFOUmym6fQ/hlDCPh/iejzHHQCfklbQ5Aj6GmlRV wHpoIObnOzHYxWYNiRsqWT7Wd6M39dsD7Op6w= Received: by 10.68.19.4 with SMTP id a4mr427496pbe.78.1315080256150; Sat, 03 Sep 2011 13:04:16 -0700 (PDT) X-BeenThere: lojban@googlegroups.com Received: by 10.142.3.17 with SMTP id 17ls10992298wfc.2.gmail; Sat, 03 Sep 2011 13:04:15 -0700 (PDT) Received: by 10.68.32.194 with SMTP id l2mr1818568pbi.14.1315080255587; Sat, 03 Sep 2011 13:04:15 -0700 (PDT) Received: by 10.68.32.194 with SMTP id l2mr1818567pbi.14.1315080255578; Sat, 03 Sep 2011 13:04:15 -0700 (PDT) Received: from chain.digitalkingdom.org (digitalkingdom.org. [173.13.139.234]) by gmr-mx.google.com with ESMTPS id ll18si3991306pbb.0.2011.09.03.13.04.15 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 03 Sep 2011 13:04:15 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of rlpowell@digitalkingdom.org designates 173.13.139.234 as permitted sender) client-ip=173.13.139.234; Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.72) (envelope-from ) id 1QzwRq-00017s-3Q for lojban@googlegroups.com; Sat, 03 Sep 2011 13:04:14 -0700 Date: Sat, 3 Sep 2011 13:04:14 -0700 From: Robin Lee Powell To: lojban@googlegroups.com Subject: Re: [lojban] Regular Language Message-ID: <20110903200414.GM9995@digitalkingdom.org> References: MIME-Version: 1.0 In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Original-Sender: rlpowell@digitalkingdom.org X-Original-Authentication-Results: gmr-mx.google.com; spf=pass (google.com: best guess record for domain of rlpowell@digitalkingdom.org designates 173.13.139.234 as permitted sender) smtp.mail=rlpowell@digitalkingdom.org Reply-To: lojban@googlegroups.com Precedence: list Mailing-list: list lojban@googlegroups.com; contact lojban+owners@googlegroups.com List-ID: X-Google-Group-Id: 1004133512417 List-Post: , List-Help: , List-Archive: Sender: lojban@googlegroups.com List-Subscribe: , List-Unsubscribe: , Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline 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.