Encontrar rápidamente cadenas vacías que producen no terminales en un CFG

Para un lenguaje libre de contexto determinado G, que llamamos un no terminal nullable si , es decir, podemos derivar la cadena vacía de después de aplicar un número finito de producciones.$A_i$ $A_i \rightarrow^* \epsilon$$A_i$

Hay un algoritmo simple para determinar qué no terminales de una gramática son anulables, como se puede encontrar aquí :

Comenzamos considerando todos los no terminales como no anulables. todos los como anulables si hay una producción . Luego hacemos un bucle sobre todas las demás producciones excluyendo las producciones con un terminal en ellas, y marcamos como anulable si todos son anulables. Seguimos haciendo este bucle hasta que terminemos un bucle sin marcar ningún no terminal como anulable.A i → ϵ A i → B 1 B 2 … B k A i B $A_i$$A_i \rightarrow \epsilon$$A_i \rightarrow B_1 B_2 \dots B_k$$A_i$$B_i$

Mi problema con este algoritmo es que tiene un tiempo de ejecución: un peor de los casos es por ejemplo , , , ..., , .A 1 → A 2 A 2 → A 3 A 3 → A 4 A n - 1 → A n A n → $O(n^2)$$A_1 \rightarrow A_2$$A_2 \rightarrow A_3$$A_3 \rightarrow A_4$$A_{n-1} \rightarrow A_n$$A_n \rightarrow \epsilon$

¿Existe un algoritmo para este problema con un mejor tiempo de ejecución que ?$O(n^2)$

¿No se puede implementar ese algoritmo en tiempo lineal de la siguiente manera? (Advertencia: no he revisado esto con demasiada atención, por lo que es probable que haya errores).

En lo que sigue cada vez que digo "producción" me refiero a incluir solo aquellos que no incluyen terminales. Construir una lista, para cada no terminal, de las producciones que aparece. Para cada producción dejo c i contar cuántas no terminales distintos en el lado derecho están marcados como no anulable. Supongamos que Q denota una cola de no terminales que se han marcado como nulos pero aún no procesados. Inicialice todo c i al número de no terminales distintos en el lado derecho de producción i . Inicialice todos los no terminales a no anulables. Para cada Z no terminal generada por la producción i con c i$i$$c_i$$Q$$c_i$$i$$Z$$i$ agregue Z a Q y marque Z como anulable.$c_i=0$$Z$$Q$$Z$

Mientras no está vacío, elimine una X arbitraria no terminal de Q y procese de la siguiente manera. Por cada producción j en la que X está, decremente c j . Si a c j se convierte en cero, verifique si el Y no terminal correspondiente ya se ha marcado como nulo. Si no es así, marque Y anulable y añadir Y a Q .$Q$$X$$Q$$j$$X$$c_j$$c_j$$Y$$Y$$Y$$Q$