Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| finding a string whether belongs to CFL or not mightydreams@gmail.com (wheatstone) (2010-06-22) |
| Re: finding a string whether belongs to CFL or not ott@mirix.org (Matthias-Christian Ott) (2010-06-23) |
| Re: finding a string whether belongs to CFL or not gene.ressler@gmail.com (Gene) (2010-06-25) |
| Re: finding a string whether belongs to CFL or not ott@mirix.org (Matthias-Christian Ott) (2010-06-25) |
| Re: finding a string whether belongs to CFL or not cfc@shell01.TheWorld.com (Chris F Clark) (2010-06-27) |
| Re: finding a string whether belongs to CFL or not gene.ressler@gmail.com (Gene) (2010-06-28) |
| From: | Gene <gene.ressler@gmail.com> |
| Newsgroups: | comp.compilers |
| Date: | Mon, 28 Jun 2010 17:04:30 -0700 (PDT) |
| Organization: | Compilers Central |
| References: | 10-06-068 10-06-079 10-06-080 |
| Keywords: | parse, theory |
| Posted-Date: | 29 Jun 2010 11:09:47 EDT |
> No, context-free grammars are not closed under complement, so your
> claim is only true for special cases in which the complement of a
> context-sensitive grammar might be context-free.
I'm sorry you didn't understand what I wrote. I only said the
complement of a^n b^n a^n is context free (even though the set itself
isn't by the pumping lemma for CFLs). I described how to build a CFG
for that complement. This grammar is a proof of CF-ness.
A small additional point is that you no doubt meant CFL's (rather than
CFGs) are not closed under complement. Complement is defined on
sets, and a CFG is not a set.
Return to the
comp.compilers page.
Search the
comp.compilers archives again.