Re: need help developin better sense for context free languages

"Mitch" <maharri@xxxxxxxxx> writes:

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

Don't be too sure. Lecturers (myself included) often put blindingly
obvious questions in tests to see who are completely clueless.

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.

That argument isn't very useful, as there are examples of languages
that don't seem context free, but are. For example, the complement of
{ww | w in {0,1}*} is context free (and a nice example of CF languages
not being closed under complement).

- theoretical: it is undecidable whether a language is context free
(Rice's theorem), (given some unrestricted manner of presentation, like
pseudo-mathematical English).

Much better argument, but since no nontrivial question is decidable
when you are allowed Turing complete or other unrestricted
descriptions, it doesn't say much about CF languages per se.

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

If a description is in BNF or some notation that is equivalent to (a
subset of) BNF, then the question is trivial. More interesting is if
it is decidable for languages described by regular-like languages with
side conditions on equality of substrings or lengths of substrings,
such as those often found in exam questions. The answer would
probably depend on the exact details, but I think it could be
decidable for languages of the form

{w_1 w_2 ... w_n | conditions}

where each condition is of the form w_i in \Sigma*, w_i = w_j, |w_i| <
|w_j| and negations, conjunctions and disjunctions of those. I
haven't tried to prove it, though, so it is just a hunch.

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

If you think the language is CF, you can try to make a grammar. First
try to see if you can systematically structure strings in the language
as trees (allowing multiple trees, as we're not interested in proving
non-ambiguity), then write this systemisation up as productions.

If you don't think the language is CF, you can use the pumping lemma.
Since that usually requires that you find a good string example, it
may not be easy unless you first analyse the source of why the
language is non-CF, i.e., whether two unbounded substrings must be
equal or three or more must be of the same length. Then it usually
works to choose an example where these substrings are longer than the
N given by the pumping lemma. If you are not required to give a
formal proof, just say that you need equality of two unbounded
substrings or equal lengths of three unbounded substrings.

Torben
.

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
    ... Are there any tell tale signs that it is/is not context free? ... Is there an easy way to tell starigh away if a language is context free ... tested on the use of closure properties to determine ... K chosen as the right one to use?"), With a little practice with those ...
    (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)