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

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”.

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. Supongamos que N(s)y N(t)son AFND’s para las expresiones regulares sy t,

 respectivamente.