CODEWITHSUNDEEP
computer-sciencecontext-free-grammar
user423733
user423733

Reputation: 325

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

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

Upvotes: 31

Views: 73160

Answers (3)

P Shved
P Shved

Reputation: 99254

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

Upvotes: 35

questzen
questzen

Reputation: 3287

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.

alt text

Edit A->aB and A->Ba definitions are meant to express Left and Right recursive grammars and are not to be taken literally.

Upvotes: 2

falagar
falagar

Reputation: 336

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

Upvotes: 1

Related Questions