Check if the language is Context Free or Not | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Prerequisite – Pumping Lemma, How to identify if a language is regular or not

We typically face questions to identify which of the given languages are context free. In case of regular languages, it is comparatively easy to answer this, but for Context Free languages, it is tricky sometimes. Pumping Lemma provides us with ability to perform negative test, i.e. if a language doesn’t satisfy pumping lemma, then we can definitely say that it is not context free, but if it satisfies, then the language may or may not be context free. Pumping Lemma is more of a mathematical proof, takes more time and to apply it on context free languages is a tedious task and finding out counter example for complex language expressions is not much handful. We can address this problem very quickly, based on common observations and analysis:

1. Every regular language is context free.
   Example – { a^m b^l c^k dⁿ | m, l, k, n >= 1 } is context free, as it is regular too.
2. Given an expression such that it is possible to obtain a center or mid point in the strings, so we can carry out comparison of left and right sub-parts using stack.
   ➤ Example 1 – L = {aⁿ bⁿ | n >= 1} is context free, as we can push a’s and then we can pop a’s for each occurrence of b.
   ➤ Example 2 – L = {a^m bⁿ c(m+n)} is context free. We can rewrite it as { a^m bⁿ cⁿ c^m}.
   ➤ Example 3 – L = { aⁿ b^{(2n)} } is context free, as we can push two a’s and pop an a for each occurrence of b. Hence, we get a mid-point here as well.
   ➤ Example 4 – L = { aⁿ bⁿ cⁿ } is not context free.
3. Given expression is a combination of multiple expressions with mid-points in them, such that each sub-expression is independent of other sub-expressions, then it is context free.
   ➤ Example 1 – L = { a^m b^m cⁿ dⁿ } is context free. It contains multiple expressions with a mid-point in each of them.
   ➤ Example 2 – L = { a^m bⁿ c^m dⁿ } is not context free.
4. Given expression consists of an operation where mid-point could be found along with some independent regular expressions in between, results into context free language.
   ➤ Example – L = { a^m bⁱ c^m d^k } is a context free language.
   Here, we have bⁱ and d^k as independent regular expressions in between, which doesn’t affect the stack.
5. An expression that doesn’t form a pattern on which linear comparison could be carried out using stack is not context free language.
   ➤ Example 1 – L = { a^m bⁿ² } is not context free.
   ➤ Example 2 – L = { aⁿ b²ⁿ } is not context free.
   ➤ Example 3 – L = { aⁿ² } is not context free.
   ➤ Example 4 – L = { a^m | m is prime } is not context free.
6. An expression that involves counting and comparison of three or more variables independently is not context free language, as stack allows comparison of only two variables at a time.
   ➤ Example 1 – L = { aⁿ bⁿ cⁿ } is not context free.
   ➤ Example 2 – L = { w | na(w) = nb(w) = nc(w) } is not context free.
   ➤ Example 3 – L = { aⁱ b^j c^k | i > j > k } is not context free.
7. A point to remember is counting and comparison could only be done with the top of stack and not with bottom of stack in Push Down Automata, hence a language exhibiting a characteristic that involves comparison with bottom of stack is not a context free language.
   ➤ Example 1 – L = { a^m bⁿ c^m dⁿ } is not context free. Pushing a’s first then b’s. Now, we will not be able to compare c’s with a’s as the top of the stack has b’s.
   ➤ Example 2 – L = { WW | W belongs to {a, b}* } is not context free.
   One might think to draw a non-deterministic push down automaton, but it will not help as first symbol will be at bottom of the stack and when the second W starts, we will not be able to compare it with the bottom of stack.
8. If we can find mid-point in the expression even in a non-deterministic way, then it is context free language.
   ➤ Example 1 – L = { W W^r | W belongs to {a, b}* } is context free language.
   ➤ Example 2 – L = { aⁱ b^j c^k d^l | i=k or j=l } is a context free language.