How can I determine if a language is context free or not?


How can I know whether the languages are context free or not?


Answers:


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-free; 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 notes at Wikipedia).

This lemma is a corollary 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).