Algoritmo de Thompson

Algoritmo de Thompson

El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no determinístico con transiciones vacías (AFND-ε) a partir de expresiones regulares (ER).

Algoritmo

Dadas las reglas que definen las expresiones regulares se pueden escribir como AFND-e:

  • Φ es una expresión regular que describe el lenguaje vacío: no hay AFD para este lenguaje ya que es vacío
  • ε es una expresión regular que describe el lenguaje {ε}, que es un lenguaje que únicamente contiene la cadena vacía: el autómata que reconoce este lenguaje es aquel que el estado inicial también es final.
  • si "a" esta en el alfabeto, "a" (sin comillas) es una expresión regular que describe el lenguaje {a}: el autómata que reconoce este lenguaje tiene definida una transición desde el estado inicial hacia un estado final.
  • si existen r y s expresiones regulares r es una expresión regular que describe L(r) y s es una expresión regular que describe L(s)
    • r+s describe L(r) U L(s) (lenguaje generado por r union lenguaje generado por s)
    • r.s describe L(r). L(s) (lenguaje generado por r concatenado lenguaje generado por s)
    • r* describe L(r)* (lenguaje generado por r clausura)

Las precedencias de operador son *,., +.

Para la suma de ER el AFND-ε se arma de la siguiente manera:

Suma ER AFND-e.png

Donde M1 y M2 son los AFND-ε que se suman.

Para el operador. de ER el AFND-ε se arma de la siguiente manera:

Concat ER AFND-e.jpg

Donde M1 y M2 son los AFND-ε que se concatenan.

Para el operador * de una ER el AFND-e se arma de la siguiente manera:

Clausura ER AFND-e.jpg

Donde M1 es el AFND-ε que se le aplica la clausura.

Herramientas

Existen varios programas que realizan este algoritmo y de hecho es habitual también pasar de AFND-e a AFND y de AFND a AFD, también suele ocurrir que el AFD no sea mínimo y se usa otro algoritmo para conseguir el AFD mínimo.

Cualquier ER puede ser reconocida por un AFD ya que los lenguaje regulares de tipo 3 son reconocidos por un AFD como autómata mas restrictivo habiendo equivalencia entre no determinismo y determinismo. Generalmente los programas que aplican el algoritmo suelen transformar una ER a AFD mínimo.

Algunos programas son:

Enlaces externos

Apunte de Gramaticas Regulares y Expresiones Regulares UNICEN


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • Ajedrez por computadora — GNU Chess 5.07 en interface WinBoard 4.2.7. En el siglo XVIII empezó a difundirse la idea de crear una computadora capaz de jugar al ajedrez. En el año 1769, un jugador de ajedrez autómata llamado El Turco[1] …   Wikipedia Español

  • Alineamiento de secuencias — Un alineamiento de secuencias en bioinformática es una forma de representar y comparar dos o más secuencias o cadenas de ADN, ARN, o estructuras primarias proteicas para resaltar sus zonas de similitud, que podrían indicar relaciones funcionales… …   Wikipedia Español

  • Bioinformática — Saltar a navegación, búsqueda La bioinformática, según una de sus definiciones más sencillas, es la aplicación de tecnología de computadores a la gestión y análisis de datos biológicos.[1] Los términos bioinformática, biología computacional y, en …   Wikipedia Español

  • Historia de la computación — Saltar a navegación, búsqueda La computadora no es un invento de alguien en particular, sino el resultado evolutivo de ideas y realizaciones de muchas personas relacionadas con áreas tales como la electrónica, la mecánica, los materiales… …   Wikipedia Español

  • Anexo:Historia de la computación — La computadora u ordenador, no es un invento de alguien en particular, sino el resultado evolutivo de ideas y realizaciones de muchas personas relacionadas con áreas tales como la electrónica, la mecánica, los materiales semiconductores, la… …   Wikipedia Español

  • Alineamiento múltiple de secuencias — Un alineamiento múltiple de secuencias (MSA, por sus siglas en inglés) es un alineamiento de tres o más secuencias biológicas, generalmente proteínas, ADN o ARN. En general, se asume que el conjunto de secuencias de consulta que se ingresa como… …   Wikipedia Español

  • Clustal — Desarrollador Gibson T. (EMBL), Thompson J. (CNRS), Higgins D. (University College Dublin) Clustal Información general Última versión estable 2.1 1 …   Wikipedia Español

  • Base de datos de tablas de finales — Saltar a navegación, búsqueda Una interfaz típica para solicitar una base de datos de tablas. Para cada movimiento del Blanco, la base de datos devuelve el número de movimientos necesarios para ganar. Rc6 y Da6+ gana en cinco movimientos, por lo… …   Wikipedia Español

  • UTF-8 — (8 bit Unicode Transformation Format) es un formato de codificación de caracteres Unicode e ISO 10646 utilizando símbolos de longitud variable. UTF 8 fue creado por Robert C. Pike y Kenneth L. Thompson. Está definido como estándar por la RFC 3629 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”