Proving a Language Is Not a CFL
- From: Bernd L <berndlosert@xxxxxxxxx>
- Date: Sun, 4 May 2008 08:34:58 -0700 (PDT)
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?
.
- Follow-Ups:
- Re: Proving a Language Is Not a CFL
- From: Ben Bacarisse
- Re: Proving a Language Is Not a CFL
- From: Michal Przybylek
- Re: Proving a Language Is Not a CFL
- From: Jussi Piitulainen
- Re: Proving a Language Is Not a CFL
- Prev by Date: Re: Another approach to decide on existence of a real root for Univariate Polynomials with Integer Coefficients, and a possible Multivariate extension for 3-SAT
- Next by Date: Re: CYK & Context-Free Expressions
- Previous by thread: Re: Another approach to decide on existence of a real root for Univariate Polynomials with Integer Coefficients, and a possible Multivariate extension for 3-SAT
- Next by thread: Re: Proving a Language Is Not a CFL
- Index(es):
Relevant Pages
|
