AUTOMATAS FINITOS 3.4

Representacion de Expresion Regular usando AFND

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 construir verificadores o buscadores eficientes a partir de ERs.

3.

 

Libertad de espíritu en ciencia y tecnología

Ingeniería en Sistemas Computacionales

11

3.4 Representación de ER usando AFND

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 construir verificadores 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 parte que 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 ejemplo que acabamos de dar, aplicado sobre E1 = a

⋆ 

 b, reconocería la cadena x = aa

 

Libertad de espíritu en ciencia y tecnología

Ingeniería en Sistemas Computacionales

12

 Representación de la expresión regular

Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -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 much

as variantes de este algoritmo denominado “Algoritmo de Thompson”.

Este algoritmo es dirigido por sintaxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. Sup

ongamos que N(s)y N(t)son AFND’s para las expresiones regulares sy t,

 respectivamente. a)

 

Para la expresión regular s | t(alternancia), construir el siguiente AFND, N(s|t)