Re: need help developin better sense for context free languages

I think Torben's post has a bunch of good ideas. In real-life
(i.e. outside of courses and exams), this question is almost never
asked. And, not having been in school since probably before you were
born, I can't tell you what lecturers ask. However, there aren't
really very many patterns, so you can almost memorize all the
cases. ww^R works because you can push w onto the stack and pop it
back off, so palindromes are solvable (and ww doesn't because you need
to push onto a queue rather than a stack). Same thing goes for
a^jb^j, push a's and pop off to match b's. a^jb^jc^j doesn't because
you only have one stack, so you can't both pop when seing b's to match
the a^jb^j part and push at the same time to match the b^jc^j part.
However, there aren't a lot of more known tricks than that, which hold
only for CFG's.

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?).

Hope this helps,
-Chris

*****************************************************************************
Chris Clark Internet : compres@xxxxxxxxxxxxx
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
.

Relevant Pages

  • Re: Is it wise to push all-in early in a tournament?
    ... The best times to make a push play ... But why call when you can push and take down a nice pot when your opponent ... But remember that if this "big bet" is a significant portion of your stack, ... I consider it my goal in any tournament to do the latter as much as ...
    (rec.gambling.poker)
  • Re: Is it wise to push all-in early in a tournament?
    ... whether or not the rest of the table is splashing chips around. ... I may push more than I want to and you may be more conservative than ... Do I want to play this opponent after the flop? ... push at anytime and I may not want to risk my stack on a suckout when I ...
    (rec.gambling.poker)
  • Virtual machine: assembly instructions
    ... push; Push the address of the first variable onto the stack ... itof: convert integer to float ... If top+1 of int stack is less than top; push true else push false ...
    (comp.programming)
  • Re: Building Unification Table - tranforming prolog like notation into lisp notation
    ... |> problem comes from tranlating prolog notation into lisp notation. ... ;; Here is a quickly done stack based solution for the problem Slobodan ... (defstruct composite-term str indices) ... (push (cons (composite-term-str item) ...
    (comp.lang.lisp)
  • Re: Free word order
    ... > Frontwardness of language: Going S O V. ... I agree that SVO is a bit mixed-up for me as a native speaker of a SOV ... In a SOV language by analogy, the arguments are pushed to the stack ... no idea so push it ...
    (sci.lang)