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