Prev: 2d cross-correlation / convolution
Next: domains for typed lambda calculi
From: Bernd L on 4 May 2008 11:34
This is a problem from Sipser's book which I'm unable to answer:

If A is a CFL and B is a regular language, then the intersection of A
and B is context free. Given this result, show that the language C =
{w : w in {a, b, c}* and contains an equal number of a's, b's and c's}
is not a CFL.

Let D be the language described by the regex (abc)*. This language is
regular and is a subset of C so the intersection of C and D is D which
is also context free. What gives?
From: Jussi Piitulainen on 4 May 2008 12:48
Bernd L writes:

> This is a problem from Sipser's book which I'm unable to answer:
>
> If A is a CFL and B is a regular language, then the intersection of
> A and B is context free. Given this result, show that the language C
> = {w : w in {a, b, c}* and contains an equal number of a's, b's and
> c's} is not a CFL.
>
> Let D be the language described by the regex (abc)*. This language
> is regular and is a subset of C so the intersection of C and D is D
> which is also context free. What gives?

That's not the regex that gives the result. Another one gives a
well-known non-CFL.
From: Michal Przybylek on 4 May 2008 12:52
Dnia 04-05-2008 o 17:34:58 Bernd L <berndlosert(a)gmail.com> napisa�(a):

> This is a problem from Sipser's book which I'm unable to answer:
>
> If A is a CFL and B is a regular language, then the intersection of A
> and B is context free. Given this result, show that the language C =
> {w : w in {a, b, c}* and contains an equal number of a's, b's and c's}
> is not a CFL.
>
> Let D be the language described by the regex (abc)*. This language is
> regular and is a subset of C so the intersection of C and D is D which
> is also context free. What gives?

Nothing. Try a different language.

HINT: Does it exist a regular language R, such that C \cap R = {a^n b^n
c^n : n \in Nat} ?


mp
From: Ben Bacarisse on 4 May 2008 13:35
Bernd L <berndlosert(a)gmail.com> writes:

> This is a problem from Sipser's book which I'm unable to answer:
>
> If A is a CFL and B is a regular language, then the intersection of A
> and B is context free. Given this result, show that the language C =
> {w : w in {a, b, c}* and contains an equal number of a's, b's and c's}
> is not a CFL.
>
> Let D be the language described by the regex (abc)*. This language is
> regular and is a subset of C so the intersection of C and D is D which
> is also context free. What gives?

You have the logic backwards. The statement one is to assume is that:

(A is CF) and (B is regular) => (A /\ B) is CF.

We are told to expect that not(C is CF). You show an example of D
that is regular and are surprised that (C /\ D) is CF but the
implication above is one way. It does not prohibit

not(C is CF) and (D regular) and (C /\ D) is CF

The theorem says that C's intersection with *all* regular languages is
CF. I image that you are expected to find one (or more) regular
languages whose intersection with C is clearly *not* a CFL. Does that
help?

--
Ben.
From: Bernd L on 4 May 2008 13:44
On May 4, 1:35 pm, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote:
> We are told to expect that not(C is CF). You show an example of D
> that is regular and are surprised that (C /\ D) is CF but the
> implication above is one way. It does not prohibit
>
> not(C is CF) and (D regular) and (C /\ D) is CF
>
> The theorem says that C's intersection with *all* regular languages is
> CF. I image that you are expected to find one (or more) regular
> languages whose intersection with C is clearly *not* a CFL. Does that
> help?

I understand now. Thanks.
 |  Next  |  Last
Pages: 1 2
Prev: 2d cross-correlation / convolution
Next: domains for typed lambda calculi