Languages
By putting together Theorems 5.2 and 6.6, we have already established the
existence of a membership algorithm for context-free languages. This is of
course an essential feature of any language family useful in practice. Other
simple properties of context-free languages can also be determined. For the
purpose of this discussion, we assume that the language is described by its
grammar.
Theorem 8.6
Given a context-free grammar G =(V,T,S,P), there exists an algorithm for
deciding whether or not L (G) is empty.
Proof: For simplicity, assume that λ L (G). Slight changes have to be made in
the argument if this is not so. We use the algorithm for removing useless
symbols and productions. If S is found to be useless, then L (G) is empty; if not,
then L (G) contains at least one element.
Theorem 8.7
Given a context-free grammar G =(V, T, S, P), there exists an algorithm for
determining whether or not L (G) is infinite.
Proof: We assume that G contains no λ-productions, no unit-productions, and no
useless symbols. Suppose the grammar has a repeating variable in the sense that
there exists some A V for which there is a derivation
Since G is assumed to have no λ-productions and no unit-productions, x and y
cannot be simultaneously empty. Since A is neither nullable nor a useless
symbol, we have
and
By putting together Theorems 5.2 and 6.6, we have already established the
existence of a membership algorithm for context-free languages. This is of
course an essential feature of any language family useful in practice. Other
simple properties of context-free languages can also be determined. For the
purpose of this discussion, we assume that the language is described by its
grammar.
Theorem 8.6
Given a context-free grammar G =(V,T,S,P), there exists an algorithm for
deciding whether or not L (G) is empty.
Proof: For simplicity, assume that λ L (G). Slight changes have to be made in
the argument if this is not so. We use the algorithm for removing useless
symbols and productions. If S is found to be useless, then L (G) is empty; if not,
then L (G) contains at least one element.
Theorem 8.7
Given a context-free grammar G =(V, T, S, P), there exists an algorithm for
determining whether or not L (G) is infinite.
Proof: We assume that G contains no λ-productions, no unit-productions, and no
useless symbols. Suppose the grammar has a repeating variable in the sense that
there exists some A V for which there is a derivation
Since G is assumed to have no λ-productions and no unit-productions, x and y
cannot be simultaneously empty. Since A is neither nullable nor a useless
symbol, we have
and