Expresiones Regulares y Autómatas
Páginas: 4 (974 palabras)
Publicado: 3 de diciembre de 2013
AUTÓMATAS FINITOS
AUTÓMATAS FINITOS
O máquinas de estado finito, son una manera
matemática para describir clases particulares de
algoritmos.
Se utilizan para describir el procesode
reconocimiento de patrones en cadenas de
entrada, y de este modo se utiliza para construir
analizadores léxicos.
AUTÓMATAS FINITOS(2)
Ejemplo: el patrón para identificadores comose
define comúnmente en los lenguajes está dado
por: identificador = letra(letra|digito)*
El proceso de reconocer una cadena así se puede
describir mediante el diagrama:
AUTÓMATAS FINITOS(3)
En el diagrama los círculos 1 y 2 representan
estados, que son localidades en el proceso de
reconocimiento que registran cuánto ya se ha visto.
Las líneas con flechas representantransiciones que
registran un cambio de un estado a otro en una
coincidencia del carácter o caracteres mediante los
cuales son etiquetados.
En el diagrama el estado 1 es el estado de inicio, porconveniencia se indica dibujando una línea con flechas sin
etiqueta que proviene de “alguna parte”.
El estado e representa el punto en el cual se ha igualado
una sola letra, una vez aquí cualquiernúmero de letras y /
o dígitos se puede ver, y una coincidencia de estos nos
regresa al estado 2.
AUTÓMATAS FINITOS(4)
Los estados que representan el fin del proceso de
reconocimiento,donde se declara un éxito, se
denominan estados de aceptación, se indican
dibujando un borde con línea doble alrededor del
estado en el diagrama. (puede haber mas de uno)
AUTÓMATAS FINITOSDETERMINÍSTICOS
Un DFA M se compone de un alfabeto ∑, un
conjunto de estados S, una función de transición
T: S ⊗ ∑ -> S, un estado de inicio s0 ∈ S y un
conjunto de estaos de aceptación A ⊂ S. ellenguaje aceptado por M, escrito como L(M), se
define como el conjunto de cadenas de caracteres
c1,c2,…cn con dada ci ∈ ∑, tal que existen estados
con sn como un elemento de A ( un estado de...
AUTÓMATAS FINITOS
O máquinas de estado finito, son una manera
matemática para describir clases particulares de
algoritmos.
Se utilizan para describir el procesode
reconocimiento de patrones en cadenas de
entrada, y de este modo se utiliza para construir
analizadores léxicos.
AUTÓMATAS FINITOS(2)
Ejemplo: el patrón para identificadores comose
define comúnmente en los lenguajes está dado
por: identificador = letra(letra|digito)*
El proceso de reconocer una cadena así se puede
describir mediante el diagrama:
AUTÓMATAS FINITOS(3)
En el diagrama los círculos 1 y 2 representan
estados, que son localidades en el proceso de
reconocimiento que registran cuánto ya se ha visto.
Las líneas con flechas representantransiciones que
registran un cambio de un estado a otro en una
coincidencia del carácter o caracteres mediante los
cuales son etiquetados.
En el diagrama el estado 1 es el estado de inicio, porconveniencia se indica dibujando una línea con flechas sin
etiqueta que proviene de “alguna parte”.
El estado e representa el punto en el cual se ha igualado
una sola letra, una vez aquí cualquiernúmero de letras y /
o dígitos se puede ver, y una coincidencia de estos nos
regresa al estado 2.
AUTÓMATAS FINITOS(4)
Los estados que representan el fin del proceso de
reconocimiento,donde se declara un éxito, se
denominan estados de aceptación, se indican
dibujando un borde con línea doble alrededor del
estado en el diagrama. (puede haber mas de uno)
AUTÓMATAS FINITOSDETERMINÍSTICOS
Un DFA M se compone de un alfabeto ∑, un
conjunto de estados S, una función de transición
T: S ⊗ ∑ -> S, un estado de inicio s0 ∈ S y un
conjunto de estaos de aceptación A ⊂ S. ellenguaje aceptado por M, escrito como L(M), se
define como el conjunto de cadenas de caracteres
c1,c2,…cn con dada ci ∈ ∑, tal que existen estados
con sn como un elemento de A ( un estado de...
Leer documento completo
Regístrate para leer el documento completo.