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

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:
>>> 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.

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?

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