How can I know whether the languages are context free or not?
+1
A:
You need a grammar for the language to determine if it is context free. A grammar is context free if all it's productions has form "(non-terminal) -> sequence of terminals and non-terminals".
falagar
2010-08-18 08:15:54
Yes thanks. Then 0^n 1^n is context free. so The complement of {(0^n1^n)^m | m, n > 0} is Context Free or not.
2010-08-18 08:19:56
It should be pointed out that just because you can come up with non-context-free grammar for a language that does not mean that there is no context free grammar for that language. In short you can only use constructing a grammar to show that a language is context-free, not to show that it isn't.
sepp2k
2010-08-18 10:16:34
+4
A:
First, you should attempt to build a context-free grammar that forms the language in subject. A grammar is context-free if left-hand sides of all productions contain exactly one non-terminal symbol. By definition, if one exists, then the language is context-free.
An equivalent construct would be a pushdown automaton. It's the same as DFA, but with a stack available. It may be easier to build than a grammar.
However, if you fail to build a grammar or an automaton, it doesn't mean that a language is not context-freee; perhaps, it's just you who can't build a grammar tricky enough (for example, I once spent about 7 hours to build a grammar for a tricky language).
If you start to doubt if the language is context-free, you should use a so-called "pumping lemma for context-free languages". It describes a property of all context-free languages, and if your language violates it, then it's definitely not context-free (see usage noets at Wikipedia).
This lemma is a colloraly of Ogden's lemma. So Ogden's is more powerful, and if you failed to apply pumping lemma, you might try Ogden's (it's used the same way).
Pavel Shved
2010-08-18 08:20:16
All this is good, but you do realise that none of this completely determines an answer, right? What if you can't find a context-free grammar, and Ogden's lemma doesn't contradict any known property of your language? You're still stuck with the problem. (Which I believe is hard, so your answer is perhaps as good as it gets; just pointing out that it's not exhaustive.)
ShreevatsaR
2010-08-20 05:33:23
@ShreevatsaR, exactly. It may happen that none of the above works. But I actually don't know what to do in that case.
Pavel Shved
2010-08-20 05:46:29
+1
A:
Edit
As suggested in the comments to prove a language to be non-CFG, I believe is by using an ogdens' lemma. The inherent misinterpretation contained in my earlier answer is to be excused :) Retaining the earlier answer for lurkers.
Old answer
By looking at the grammar and rules used! As seen from the image (courtesy wikipedia chomsky hierarchy). Only regular languages are non-context-free. Implying anything which uses things of form A->aB or A->Ba alone are not context free.
Edit A->aB and A->Ba definitions are meant to express Left and Right recursive grammars and are not to be taken literally.
questzen
2010-08-18 08:21:44
Technically, regular languages are context-free, but I agree that the term "context-free" is often used to mean "context-free, but not regular" - i.e. that the labels in the diagram are applied to the smallest enclosing areas they're in, rather than the smallest circles they're in.
reinierpost
2010-08-18 10:08:32
"Only regular languages are non-context-free." What? I think you're reading the diagram the wrong way around. Regular languages are a subset of context-free languages and thus they definitely are context-free. However most context-sensitive languages are *not* context-free which makes the context-sensitive languages a strict superset of context-free languages.
sepp2k
2010-08-18 10:14:41
Sepp2k, I meant those in terms of the expressive power. For instance expressive power of context free languages is far higher than those of regular languages. A regular grammar **will not** have the same expressive power. However a CSL can be more expressive than a CFG. So a CSL is definitely a candidate for CFG but RG is not.
questzen
2010-08-18 11:15:43
@questzen: The question was how to show whether a language is context-free. A language is context-free if it is within the area labeled context-free in your diagram - including the area labeled regular, which is entirely contained within the context-free area. It is not context-free if it is outside the area. If the OP reads your answer he might be inclined to prove context-freeness by proving non-regularness (which is basically what you told him to do), which will get him a failing grade.
sepp2k
2010-08-18 11:29:34
@Reinierpost, I have edited my answer to reflect a more accurate stance
questzen
2010-08-20 05:23:07
@questzen, My point was that the OP may well share your initial use of the term, and therefore may really mean (if anything specific is meant at all) to ask how to prove that a context-free language is not regular, and that your reply is valuable for that reason.
reinierpost
2010-08-20 07:45:13