Automatas finitos y expresiones regulares
Páginas: 3 (682 palabras)
Publicado: 19 de septiembre de 2014
Autómatas finitos y expresiones regulares.
Un autómata finito es un modelo matemático de un sistema, con entradas y salidas discretas. Este sistema puede estar en cualquiera de un número finitode configuraciones o estados.
El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores.Un autómata finito FA consiste en un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto ∑.
Para cada símbolode entrada existe exactamente una transición a partir de cada estado.
A un FA se le asocia un grafo dirigido, conocido como diagrama de transiciones de la manera siguiente.
Los vértices del grafocorresponden a los estados del FA.
Si existe una transición del estado q al p sobre la entrada a, entonces existe un arco con etiqueta a que va del estado q al p, en el diagrama de transiciones.
ElFA acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce del estado inicial a un estado de aceptación.
Q es un conjunto finito de estados.
∑ es unalfabeto de entrada finito.
q 0 elemento de Q, el estado inicial.
F conjunto de estados finales.
Delta es la función de transición que transforma Q X ∑ en Q. Delta es un estado para cada estado q ysímbolo de entrada a.
Se visualiza a un FA como un control finito, que se encuentra en algún estado de Q, y que lee una secuencia de símbolos de ∑ escritos en una cinta.
Un lector puede suponer que:Q es un conjunto de estados. Los símbolos q y p, con o sin subíndices, son estados. q 0 es el estado inicial.
∑ es el alfabeto de entrada. Los símbolos a y b, con o sin subíndices, y los dígitos sonsímbolos de entrada.
Delta es una función de transición.
F es un conjunto de estados finales.
W,x,y y z, con o sin subíndices, son cadenas de símbolos de entra.
Un lenguaje es un conjunto...
Un autómata finito es un modelo matemático de un sistema, con entradas y salidas discretas. Este sistema puede estar en cualquiera de un número finitode configuraciones o estados.
El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores.Un autómata finito FA consiste en un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto ∑.
Para cada símbolode entrada existe exactamente una transición a partir de cada estado.
A un FA se le asocia un grafo dirigido, conocido como diagrama de transiciones de la manera siguiente.
Los vértices del grafocorresponden a los estados del FA.
Si existe una transición del estado q al p sobre la entrada a, entonces existe un arco con etiqueta a que va del estado q al p, en el diagrama de transiciones.
ElFA acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce del estado inicial a un estado de aceptación.
Q es un conjunto finito de estados.
∑ es unalfabeto de entrada finito.
q 0 elemento de Q, el estado inicial.
F conjunto de estados finales.
Delta es la función de transición que transforma Q X ∑ en Q. Delta es un estado para cada estado q ysímbolo de entrada a.
Se visualiza a un FA como un control finito, que se encuentra en algún estado de Q, y que lee una secuencia de símbolos de ∑ escritos en una cinta.
Un lector puede suponer que:Q es un conjunto de estados. Los símbolos q y p, con o sin subíndices, son estados. q 0 es el estado inicial.
∑ es el alfabeto de entrada. Los símbolos a y b, con o sin subíndices, y los dígitos sonsímbolos de entrada.
Delta es una función de transición.
F es un conjunto de estados finales.
W,x,y y z, con o sin subíndices, son cadenas de símbolos de entra.
Un lenguaje es un conjunto...
Leer documento completo
Regístrate para leer el documento completo.