ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER →AFND → AFD → ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construirverificadores o buscadores eficientes a partir de ERs.
3.4
Definición
La función Th convierte ERs en AFNDs según las siguientes reglas.
Prueba
Es fácil verificarlo por inspección y aplicando inducción estructural. La única parteque puede causar problemas es la clausura de Kleene, donde otros esquemas alternativos que podrían
sugerirse (por ejemplo M = (K1, Σ, ∆1
∪
{(f1, ε, s1), (s1, ε, f1)}, s1, {f1}) tienen el
problema de permitir terminar un recorrido de Th(E1) antes de tiempo. Por ejemplo el ejemploque acabamos de dar, aplicado sobre E1 = a
⋆
b, reconocería la cadena x = aa
Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de estos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas (el alumno no tiene los prerrequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”.
No hay comentarios:
Publicar un comentario