From: Peter Suk <peter.kwangjun.suk@...>
Date: 2005-04-27T07:18:32+09:00
Subject: Re: Is Ruby grammar context free?


On Apr 26, 2005, at 4:44 PM, Eric Schwartz wrote:

> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>> Okay, this part is probably context free.  I can come up with a 
>> context
>> free grammar for something analogous:
>>
>> 	X -> S1 d | S2
>> 	S1 -> a S1 b | c
>> 	S2 -> a S2 b | <empty>
>>
>> This produces the language { a^n c b^n d } where x ^ n denotes x
>> repeated n times.
>
> Actually, the c and d are optional:

No they're not!  The whole point is to show that you can have a 
language where c is matched with a d, even though it is nested in an 
arbitrary number of ab pairs.

--Peter

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.