From: Eric Schwartz <emschwar@...>
Date: 2005-04-28T04:19:34+09:00
Subject: Re: Is Ruby grammar context free?

Peter Suk <peter.kwangjun.suk@mac.com> writes:
> On Apr 27, 2005, at 12:04 PM, Eric Schwartz wrote:
>> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>>> On Apr 26, 2005, at 4:44 PM, Eric Schwartz wrote:
>>>> Peter Suk <peter.kwangjun.suk@mac.com> writes:
>>>>> 	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.
>>
>> Okay, I freely confess to maybe just being pig-ignorant here, but if I
>> can generate { a^n b^n } from your grammar, and I don't see how that's
>> precluded from what you said above, then how are c and d required?
>
> c is matched with d.  If there is no c, there is no d, and vice versa.  
> But if there is a c, there is a d.

But they're both optional-- you can generate the string 'aa bb' from
your grammar, which is all I was saying.  It's probably irrelevant,
but then again, I mentioned that in the first place.

-=Eric
-- 
Come to think of it, there are already a million monkeys on a million
typewriters, and Usenet is NOTHING like Shakespeare.
		-- Blair Houghton.