Give an algorithm to determine if a string w is in a context-free language L given a grammar for the language. The algorithm does not need to be efficient.
Give an
In case of regular languages, it is comparatively easy , but for Context Free languages. 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.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
