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

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.

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