From lojban+bncCK30vq5WEOyFi-gEGgSoIdAu@googlegroups.com Fri Dec 10 16:17:01 2010 Received: from mail-px0-f189.google.com ([209.85.212.189]) by chain.digitalkingdom.org with esmtp (Exim 4.72) (envelope-from ) id 1PRD8x-00084G-DB; Fri, 10 Dec 2010 16:17:00 -0800 Received: by pxi19 with SMTP id 19sf1356263pxi.16 for ; Fri, 10 Dec 2010 16:16:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=beta; h=domainkey-signature:received:x-beenthere:received:received:received :received:received-spf:received: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:list-post:list-help:list-archive:sender:list-subscribe :list-unsubscribe:content-type:content-disposition :content-transfer-encoding; bh=VEHk34w9kgnorZ9Vs8gjyQ7oqdgHj2yO0q+6D6P7Jaw=; b=qDorNdQca+7dzYhVJYlttY7dNS69LWkSWzxrxDydYDVgwrshV2yrkBBnHe2+i5Pez0 RVKLzydKolI9JgILE0EAb/N3HneuUJvEelrTfBfTg4yhVSS4MjUU/vGFMPyipLXD/2fk /9o73xYv26x0WIYVOxn6H226P6svX5jw2cxm8= DomainKey-Signature: a=rsa-sha1; c=nofws; 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:list-post:list-help:list-archive:sender:list-subscribe :list-unsubscribe:content-type:content-disposition :content-transfer-encoding; b=ziqgYPYnfZaOJQNv97D0rPstzrnsL096/uioJB2x9F3fQ8AsTuRJ1tXQZJrEfVRzY6 qL3BlpZo+pCDIKxp/YuCUvPzLFHZ2VH/CChQQhfd4LaSx54Fgbml2A+szm/W81VZMbXd gA1Il6Y9ry1rV2ywwEoabse74UymfzHeO883I= Received: by 10.142.56.11 with SMTP id e11mr68184wfa.58.1292026604400; Fri, 10 Dec 2010 16:16:44 -0800 (PST) X-BeenThere: lojban@googlegroups.com Received: by 10.142.207.8 with SMTP id e8ls978915wfg.2.p; Fri, 10 Dec 2010 16:16:43 -0800 (PST) Received: by 10.143.160.12 with SMTP id m12mr966461wfo.6.1292026603362; Fri, 10 Dec 2010 16:16:43 -0800 (PST) Received: by 10.143.160.12 with SMTP id m12mr966459wfo.6.1292026603339; Fri, 10 Dec 2010 16:16:43 -0800 (PST) Received: from chain.digitalkingdom.org (digitalkingdom.org [173.13.139.234]) by gmr-mx.google.com with ESMTP id n6si4006421wfl.7.2010.12.10.16.16.43; Fri, 10 Dec 2010 16:16:43 -0800 (PST) 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 1PRD8j-0007wC-6E for lojban@googlegroups.com; Fri, 10 Dec 2010 16:16:41 -0800 Date: Fri, 10 Dec 2010 16:16:41 -0800 From: Robin Lee Powell To: lojban@googlegroups.com Subject: Re: [lojban] Lojban CFG Questions Message-ID: <20101211001641.GL27025@digitalkingdom.org> References: <201012101024.39320.roman_naumann@fastmail.fm> MIME-Version: 1.0 In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) 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: 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 Content-Transfer-Encoding: quoted-printable On Fri, Dec 10, 2010 at 07:20:29PM -0300, Jorge Llamb=EDas wrote: > On Fri, Dec 10, 2010 at 6:24 AM, Roman Naumann > wrote: > > > > We have five kinds (sub)sentences. They start and terminate with > > 'a', 'b', 'c', 'd', 'e'. Inside a (sub)sentence, only > > subsentences with a letter later in alphabet may stand. ("a c c > > a" is thus valid, "b a a b" is invalid [whitespace ignored], as > > a..a is no valid subsentence of b..b). >=20 > That makes it very different from Lojban. In Lojban pretty much > any terminated structure can be found inside of any other, and > that's basically what the "terminator problem" amounts to. >=20 > > Besides elidable terminators, are there other problems why you > > think lojban can't be expressed as a CFG (without the grammar > > being way too large)? >=20 > I think ZOI is the only thing that makes Lojban non-CFG. Elidable > terminators just make for a hugely impractical CFG. >=20 > Here is an example of how to handle elidable terminators in a > small subset of Lojban: >=20 > http://groups.google.com/group/lojban/browse_thread/thread/90911b0611bb5a= 5e/555dbaf7addd93e6 >=20 > The same principle could be extended to all terminators, but the > size of the grammar would explode. Huh! I missed that. Yeah, that's 2^{number of terminators} * {current number of rules} rules or so, isn't it? Ouch. -Robin --=20 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/ --=20 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@googlegrou= ps.com. For more options, visit this group at http://groups.google.com/group/lojban= ?hl=3Den.