need help developin better sense for context free languages
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?
.
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: 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) |
|
