Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Syntax and Semantics
Context-free languages are a rich class of languages with important
applications in the theory of practice of programming
languages. However, not all languages are context-free. For example,
although the language
{ w rev(w) | w a string of a's and b's }
is context-free, the language
{ ww | w a string of a's and b's }
is not. This lecture deals with the following question:
How do we show that a language is not
context-free?
The mere fact that we might be unable to construct a PDA that
recognizes a language L does not constitute a proof of the
non-context-freeness of that language. One way to argue that
L is not context-free is to isolate a characteristic property
enjoyed by all the context-free languages, but not by L. The
so-called pumping lemma for context-free languages gives one
such property. Using the property described in the statement of the
pumping lemma, we can now formally show that many languages are not
context-free.
In particular, not all of the syntax of many programming languages can
be described using context-free grammars. For example, using
context-free grammars it is impossible to describe that variables
should be declared before they are used in a program.
For the keenest: Can you devise an algorithm to check
whether the language accepted by a CFG is infinite or not? [Hint: Work
with grammars in Chomsky Normal Form in which each non-terminal can
generate a string of terminals. Reduce the problem of deciding whether
a CNF grammar generates a finite language to a graph-theoretic problem
on a graph whose vertices are the non-terminal symbols of the
grammar.]