Re: need help developin better sense for context free languages



On Jan 25, 1:44 am, TheGist <f...@xxxxxxxxxxxx> wrote:
Suppose one is presented a language on an exam.
Are there any tell tale signs that it is/is not context free?
For example {ww | w in {0,1}*} is not context free
whereas {ww^R | w in {0,1}*} is context free (R is the reverse
of the string)
This seems counterintuitive to me. Well, I suppose one could reason
that a PDA could be constructed for ww^R but one could not do the same
for ww since one cannot test for the repeated string by popping items
off of the PDAs stack. This sort of reasoning however doesn't seem so
easy for a non context free language such as {a^jb^jc^j | j>0} .
Is there an easy way to tell starigh away if a language is context free
or not?

Short answer: No.

Long answer:

By 'student' logic, they wouldn't put it on a test if it were obvious.
Or would they?

There are two kinds of answers - practical and theoretical:
- practical: heuristically, if it's harder to think up a PDA (or even
more informally, how to make things balance like parens, or make a tree
out of all words) then it's probably not context-free. So that takes a
bit of self knowledge and experience (realizing something is hard to do
because it is hard, not because it is hard for you). Notice that in
some very informal way, ww^r is balanced but ww is not. As for
a^jb^jc^j...I have a hard time coming up with a short, intuitively
obvious justification.

- theoretical: it is undecidable whether a language is context free
(Rice's theorem), (given some unrestricted manner of presentation, like
pseudo-mathematical English). And that unfortunately is often the form
of homework exercises/exam problems. Now if the description of the
language has some very particular restriction/form (i.e. is -in- BNF,
etc) then maybe it's possible to have a decision procedure (but no
guarantee there that the algorithm has a short intuitive by-hand
version).

Since you're talkng about exams, then you're also probably going to be
tested on the use of closure properties to determine
context-freeness/non-CF-ness. At first these seem totally non-intuitive
(like "why would you use closure property K? well, it works but how was
K chosen as the right one to use?"), With a little practice with those
properties (note where they are the same or different from the closure
properties for regular languages), these do become intuitive and
convenient quick justification (after practice, that is).

Executive summary: Not really, but experience with heuristics helps.

Mitch

.

Relevant Pages

  • context free languages under SCRAMBLE operation
    ... For strings w and t, write w =' t if the symbols of w are a permutation of the symbols of t. ... which accepts the regular language to be scrambled can simply have its state transitions re-arranged to accept the SCRAMBLE of the language. ... This is de facto context free since every regular language is in turn context free. ...
    (comp.theory)
  • Re: pumping lemma for CFL
    ... >>>lemma for context free languages ... ... >>>p such that a string longer than p is uvwxy where |vwx| ... > In my mind the *essence* of the pumping lemmas is ... > while remaining in the language. ...
    (sci.math)
  • Re: need help developin better sense for context free languages
    ... Is there an easy way to tell starigh away if a language is context free ... side conditions on equality of substrings or lengths of substrings, ... tested on the use of closure properties to determine ...
    (comp.theory)
  • Re: pumping lemma for CFL
    ... you know that uvvwxxy and uvvvwxxxy are in L, ... that a long enough string in a simple enough language has a segment that can be repeated arbitrarily often while remaining in the language. ... In the regular case, it's a single segment, and in the context free case the segment may be broken by a bit in the middle that doesn't get repeated. ...
    (sci.math)