Menu
How can I know whether the languages are context free or not?
710
The language A is not context free. We have that w ∈ A and |w| = 3n ≥ n, so the pumping lemma guarantees that there must exist strings u, v, x, y, z ∈ r∗ so that w = uvxyz and the three properties in the statement of that lemma hold: (i) vy = e, (ii) |vxy| ≤ n, and (iii) uvixyiz ∈ A for all i ∈ N.
A valid (accepted) sentence in the language must follow particular rules, the grammar. A context-free language is a language generated by a context-free grammar. They are more general (and include) regular languages. The same context-free language might be generated by multiple context-free grammars.
Where α, β ∈ (N ∪ T)*, A ∈ N; γ ∈ (N ∪ T)+ and a rule of the form S → λ is allowed if the start symbol S do not appear on the right hand side of any rule. The language generated by such a grammar is called a context-sensitive language.
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).
79
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.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
