Siguiente: Aplicaciones para lenguajes libres
Subir: Propiedades, algoritmos de decisión,
Anterior: Propiedades de lenguajes libre
Índice General
- Pertenencia:
- ¿
?
sí, se puede contestar la pregunta (es decir, es un problema computable)
porque
- construimos un autómata que acepte
(por ejemplo en estado final)
- simulamos su comportamiento leyendo la palabra
- si acabamos en un estado final,
está en
, sino
no está en
dicha simulación puede tener tiempo de cálculo exponential, otra
posibilidad es
- construimos una gramática en forma normal de Chomsky
- aplicamos el algoritmo de Cocke-Younger-Kasami que resuelve
el problema en tiempo de orden
.
- Vaciedad:
- ¿
?
sí, se puede contestar la pregunta (es decir, es un problema computable)
porque
- construimos una gramática que genere
- analizamos si el símbolo inicial es útil,
si es útil, entonces
no es vacío, sino
es vacío
- Cardinalidad:
- ¿
?
sí, se puede contestar la pregunta (es decir, es un problema computable)
porque
- construimos una gramática que genere
en su forma normal de Chomsky
- analizamos el grafo de posisibles sustituciones de símbolos
para averigüar si existe un ciclo
- si existe tal ciclo, entonces
es infinito, sino
es finito
- Igualidad:
- ¿
?
no, no se puede contestar la pregunta (es decir, es un problema no computable).
- antes de entender dicha respuesta negativa,
hay que estudiar más a fondo la teoría de las Máquinas
de Turing.
Siguiente: Aplicaciones para lenguajes libres
Subir: Propiedades, algoritmos de decisión,
Anterior: Propiedades de lenguajes libre
Índice General
© 2006, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática