Check if the language is Context Free or Not

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

### 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 – { am bl ck dn | 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 = {abn | 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 = {am bn c(m+n)} is context free. We can rewrite it as { am bn cn cm}.
Example 3 – L = { an 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 = { an bn cn } 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 = { am bm cn dn } is context free. It contains multiple expressions with a mid-point in each of them.
Example 2 – L = { am bn cm dn } 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 = { am bi cm dk } is a context free language.
Here, we have bi and dk 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 = { am bn2 } is not context free.
Example 2 – L = { an b2n } is not context free.
➤ Example 3 – L = { an2 } is not context free.
➤ Example 4 – L = { am | 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 = { an bn cn } is not context free.
➤ Example 2 – L = { w | na(w) = nb(w) = nc(w) } is not context free.
➤ Example 3 – L = { ai bj ck | 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 = { am bn cm dn } 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 Wr | W belongs to {a, b}* } is context free language.
Example 2 – L = { ai bj ck dl | i=k or j=l } is a context free language.
The document Check if the language is Context Free or Not | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

## Theory of Computation

18 videos|56 docs|44 tests

## FAQs on Check if the language is Context Free or Not - Theory of Computation - Computer Science Engineering (CSE)

 1. What is Context Free Language?
Ans. A Context-Free Language (CFL) is a type of formal language that can be generated by a context-free grammar. In a CFL, every production rule has only one non-terminal symbol on the left-hand side, and it can be replaced by any sequence of symbols on the right-hand side.
 2. How is Context Free Language different from Regular Language?
Ans. The main difference between Context-Free Language (CFL) and Regular Language is that in CFL, the production rules can have variables on the left-hand side, while in Regular Language, the production rules can only have a single terminal symbol or a single terminal symbol followed by a single variable on the left-hand side.
 3. Can a Context Free Language be recognized by a Finite Automaton?
Ans. No, a Context Free Language cannot be recognized by a Finite Automaton. Context-Free Languages require a more powerful computational model, such as a Pushdown Automaton or a Turing Machine, for recognition.
 4. What is the Chomsky Hierarchy?
Ans. The Chomsky Hierarchy is a classification of formal languages based on the types of grammars that generate them. It consists of four levels: Type-0 (Unrestricted Grammar), Type-1 (Context-Sensitive Grammar), Type-2 (Context-Free Grammar), and Type-3 (Regular Grammar). Context-Free Languages belong to the Type-2 category.
 5. Are programming languages considered as Context Free Languages?
Ans. Yes, many programming languages are considered as Context Free Languages. The syntax and grammar rules of programming languages are often specified using context-free grammars, which allow for the generation of valid programs. However, it's important to note that not all programming languages are strictly context-free, as some may have additional features that go beyond the context-free language definition.

## Theory of Computation

18 videos|56 docs|44 tests

### Up next

 Explore Courses for Computer Science Engineering (CSE) exam

### Top Courses for Computer Science Engineering (CSE)

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;