```October 22

* Algorithm for determining if L(G) is empty

Recall our method of determining if a nonterminal A is useful.
We check if 1) S =>* A and
2) A =>* w

Use the second test here.

If S does not generate w for any w, then L(G) is empty.
If S =>* w then L(G) is not empty.

* Algorithm for determining if L(G) is finite

Given G, construct G' in CNF with no useless symbols such that, except
perhaps for e, L(G) = L(G').

Construct graph, vertices labeled with variables of G' and an edge from
vertex A to vertex B iff there exists C s.t. A -> BC or A -> CB
is a production.

L(G) is finite iff the graph has no directed cycles.

S -> AB
A -> BC
B -> b
C -> BD | BB
D -> a | b

Graph has no cycles, so L(G) is finite.

If D -> AB is added, there is a cycle A -> C -> D -> A and the
language is infinite.

The cycle corresponds to the production sequence

A -> BC -> BBD -> BBAB

Thus A =>* (BB)^i A B^i forall i >= 0

No symbols are useless, so B =>* w1 and A =>* w2, w1, w2 in Sigma*.
S =>* AB =>* (BB)^i A B^i B forall i >= 0
=>* (w1 w1)^i w2 w1^i w1^i, so there is an infinite number of words in L.

* Algorithm for determining if w in L(G)

O(n^3) algorithm, where n = |w| and G is fixed.

For each nonterminal A and each substring w_{ij} (beginning at position i and
having length j - if w = a1 a2 ... an then w_{ij} = ai ... a{i+j-1})
determine if A =>* w_{ij}

If forall i, j, and forall A in V, we can decide if A =>* w_{ij},
Then we can decide if w in L(G) by checking if S =>* w_{1n}.

Use notes pages 118 - 120
```