Re: need help developin better sense for context free languages

Patricia Shanahan <pats@xxxxxxx> writes:

Chris F Clark wrote:
...
But ask yourself this one, how about a^jb^jb^j? Is that a CFL or not?
Explain why. How about a^jb^kc^j, a^jbc^jc^j, or a^jb^jcb^j? If you
can answer those questions, you are likely to understand the principle
distinction. Note, if you really know your stuff, you should be able
to turn any of the above solvable problems into a grammar that
actually expresses the language "precisely"--the unsolvable ones won't
have a grammar (why not?).

I'm a bit confused by this paragraph. What do you mean by "the
unsolvable ones"?

a^jb^jb^j does have a formal grammar.

Patricia

Sorry, by unsolvable, I menat unsolvable using a PDA--that is not a
context-free-language, and by grammar I meant a CFG (context-free
grammar).


a^jb^jc^j doesn't have a CFG. I presume it must have a CSG
(context-sensitive grammar). I haven't written a CSG in years--at
least not in the traditional sense. In fact, I'd forgotten, until you
reminded me, that they exist. I don't know if I could write the CSG
for a^jb^jc^j. I can write the predicated grammar for the same, but I
don't know if there is a translation for predicated grammars to
context-sensititve ones. BTW, I think a^jb^jc^j also has a vW (aka
2-level) grammar. However, I don't generally think of either CSG's or
VW grammars or indexed grammars or tree-adjoining grammars, when I use
the word grammar. I often forget that non-context-free grammars
(aside from predicated grammars) exist.

And, that brings up an interesting (to me) question--do theory courses
(textbooks) cover predicated grammars yet? They are becoming quite
popular in parsing, but I don't know how well defined they are in
theoretical terms.

-Chris
.