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