Teoría de la Computación · Proyecto 2
Pasa una gramática libre de contexto a Forma Normal de Chomsky y usa el algoritmo CYK para saber si una frase pertenece al lenguaje.
Elija una de ejemplo o escriba la suya. Se vuelve a convertir mientras escribe.
Una regla por línea, con -> o →, y las alternativas separadas con |. Por ejemplo S -> NP VP dice que una oración es un sujeto seguido de un predicado.
Lo que aparece a la izquierda de alguna regla es un no terminal (una categoría, como NP). Todo lo demás es terminal: las palabras de la frase, que en la página salen en naranja.
El símbolo inicial es el de la primera regla. La cadena vacía se escribe e o ε.
El CYK solo acepta reglas A → B C o A → a. La conversión se hace en 6 pasos; puede ver la gramática después de cada uno.
Escriba una frase o toque un ejemplo. Los de raya verde están en el lenguaje y los de raya roja no.
Primero la frase se separa en tokens, que son las palabras o signos del alfabeto de la gramática. (id+id) queda como ( id + id ) y las mayúsculas no importan.
Si alguna palabra no está en el alfabeto, la respuesta es NO sin hacer nada más, porque ninguna regla la puede producir. Si todas están, se llena la tabla de la sección 4.
El tiempo que se muestra es solo el llenado de la tabla, promediado en varias corridas porque una sola es demasiado rápida para medirla bien.
Cada celda guarda qué símbolos pueden generar ese pedazo de la frase. La de arriba cubre la frase entera: si ahí está el símbolo inicial, la respuesta es SÍ. Con ▶ Animar llenado se ve cada corte k que se prueba y de qué dos celdas sale cada símbolo.
Se empieza por abajo. En la primera fila cada celda tiene una sola palabra, y se anotan los A que tienen una regla A → palabra.
Para las filas de arriba, el pedazo se corta en dos de todas las formas posibles: una parte izquierda de largo k y una derecha de largo l − k. Si B está en la celda de la izquierda, C en la de la derecha y existe la regla A → B C, entonces A entra a la celda.
Como cada celda solo usa celdas más bajas, que ya están calculadas, nada se calcula dos veces. Eso es la programación dinámica, y por eso el algoritmo es O(n³).
Es el mismo árbol escrito como una secuencia: en cada línea se reemplaza el no terminal de más a la izquierda (subrayado) por el lado derecho de una regla.
Arriba está el símbolo inicial y abajo las palabras. Cada nodo con sus hijos es una regla que se aplicó, y las hojas leídas de izquierda a derecha dan la frase.
El árbol que sale de la tabla está en la gramática CNF, con símbolos como T_PLUS o X_1 que nadie escribió. Por eso también se muestra traducido a la gramática original, incluyendo las ε que la conversión había quitado.
Si la frase tiene más de un árbol, es ambigua, y se pueden recorrer con ‹ ›.
Una frase por línea. Las líneas # SÍ y # NO indican qué resultado se espera.
Aquí aparece la tabla de resultados.
A → ε quiere decir que A puede desaparecer.A → B, con un solo no terminal a la derecha.