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 Formal Languages and Computability
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 context-free
grammar that generates 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] A variable in a contect-free grammar is useless if it cannot be used to derive any string of terminals. For example, the variable A is useless in the grammar
S --> aSb | a | A
A --> aA
Can you give an algorithm that, given a contect-free grammar G and a variable A, determines whether A is useless?