DHARM
322 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
11.14 DECISION PROBLEMS (DP) OF CONTEXT FREE LANGUAGES
In the previous chapter of regular expression we study a number of its decision problems and
simultaneously, we have discussed some computational tools to answer these problems.
Analogous to these problems we formulate, some of the problems for context free languages.
For some of the problems of CFLs like emptiness problem, finiteness problem and membership
problem the computational procedure exists but a lot more problems have no algorithms such
problems are known as undecidable problems of CFLs.
So, following are the decision problems:
- Finiteness problem
- Emptiness problem
- Membership problem
DP1–Finiteness Problem
Given a CFG G and its language L (G), then the question arises Is L (G) finite?
To answer the question we perform following tasks,
l First, transform the grammar G to G′ that is in CNF and
l Then make a directed graph corresponding to grammar G′. Let G′ be,
G′ = (VN, VT, S, P)
Since G′ is in CNF so it has following types of productions either A → BC or A → a whose
directed graphs are shown in Fig. 11.29(a) & (b) respectively.
B
C
A
A
()a ()b
Fig. 11.29
Directed graph is drawn from vertex (non terminal A) with an edge to each other vertices
(derived non terminals B and C) if A → BC is a production. If derived symbol is terminal like,
A → a then there is no edge shown in the directed graph corresponding to this production.
l Check for cycle/s. If the directed graph has at least a cycle then L(G) is infinite, other-
wise, L(G) is finite, (if no cycle is there).
For example, consider a grammar G of following productions
S → AB | a
A → a | AB
B → b
Since the grammar is in CNF and Fig. 11.30 shows the directed graph for it.
