218 I;1 Theory of Computer Science
(iii) Algorithm for deciding whether a regular language L is empty.
Construct a deterministic finite automaton M accepting L. We construct
the set of all states reachable from the initial state qo. We find the
states which are reachable from qo by applying a single input symbol.
These states are arranged as a row under columns corresponding to
every input symbol. The construction is repeated for every state
appearing in an earlier row. The construction terminates in a finite
number of steps. If a final state appears in this tabular column, then
L is nonempty. (Actually, we can terminate the construction as soon
as some final state is obtained in the tabular column.) Otherwise, L
is empty.
(iv) Algorithm for deciding yvhether a regular language L is infinite.
Construct a deterministic finite automaton M accepting L. L is infinite
if and only if M has a cycle.
6.7 SUPPLEMENTARY EXAMPLES
EXAMPLE 6.20
Consider a context-free grammar G with the following productions,
5 ~ A5A I B
B ~ aCb IbCa
C~ ACA IA
A ~ alb
and answer the following questions:
(a) What are the variables and terminals of G?
(b) Give three strings of length 7 in L(G).
(c) Are the following strings in L(G)?
(i) aaa
(ii) bbb
(iii) aba
(iv) abb
(d) True or false: C => bab
(e) True or false: C ::; bab
(f) True or false: C ::; abab
(g) True or false: C ::; AAA
(h) Is A in L(G)?
Solution
(a) V.\ = {5. A. B, C} and 2: = {a, b}
(b) 5 ::; A~5A~ => A~BA~ => A~aCbA~ => A~aAbA2 ::; ababbab