Jessica Lenguajes
Páginas: 7 (1717 palabras)
Publicado: 26 de marzo de 2015
¿Qué es un autómata Finito?
Un autómata finito es un conjunto de nodos y
aristas que representan trayectorias para generar
una expresión bajo un alfabeto.
Un diagrama de transición es un autómata finito.
Elementos del Autómata Finito
Los estados se identifican dentro de un circulo.
El estado inicial recibe una flecha de transición que
llega de ninguna parte.
Los estado aceptadorespueden identificarse con
doble circulo o con una cruz(igual que signo +) al
lado de ellos.
Las posibles transiciones se indicaran con flechas
que van de un estado a otro, o incluso a sí mismos.
Deben etiquetarse con el símbolo que produce el
cambio de estado.
2
Los Estado del Autómata
Entonces decimos que los estado del autómata
pueden ser:
Estados iniciales
Estados finales llamadosaceptadores
Estados finales no aceptadores
La palabra que va de un estado a otro solo
pertenece al lenguaje si el estado que la recibe es
aceptador.
Y lo contrario, si llega al final hasta un estado no
aceptador, la palabra no pertenece al lenguaje.
3
Ejemplo Gráfico de Autómata Finito
4
Supongamos un Lenguaje X
El lenguaje X es capaz de identificar la siguiente
cadena.
w=aabab
Tratemos
de
identificar
procesos del Autómata.
los
5
Explicación del Automata
Para comenzar estamos en el estado A, podemos
llamarle estado 1.
Hacemos la transición a B cuando leemos el símbolo
a.
Realizamos la siguiente transición de B hacia B
porque leemos nuevamente otro símbolo a.
Para leer b creamos otro estado D al que llegaremos
desde donde estamos que es B.
Para leer elsiguiente símbolo que es a transferimos
de nuevo hacia B.
Luego para leer el siguiente símbolo b, el autómata
regresa hasta D.
1.
2.
3.
4.
5.
6.
6
Ejemplo de Algoritmo para Autómata
7
Autómata Finito Determinista (DFA)
Es un dispositivo que puede estar en un estado de
entre un número finito de los mismos; uno de ellos
será el estado inicial y por lo menos uno será estado
de aceptación.
Tiene un flujo de entrada por el cual llegan los
símbolos de una cadena que pertenecen a un
alfabeto determinado.
8
Autómata Finito Determinista (DFA)
Es un dispositivo que puede estar en un estado de
entre un número finito de los mismos; uno de ellos
será el estado inicial y por lo menos uno será estado
de aceptación.
Tiene un flujo de entrada por el cual llegan los
símbolos de unacadena que pertenecen a un
alfabeto determinado.
9
Analizar el siguiente Ejemplo.
10
Qué podemos deducir de éste ejemplo?
Sobre las transiciones
Sobre los estados
Sobre los símbolos procesados.
11
Porqué Finito, Por qué Determinista?
Porqué finito:
Se refiere que hay un conjunto finito de estados.
Porque determinista:
La palabra determinista es porque el programa no
debetener ambigüedades, es decir, en cada
estado solo se puede dar una y solo una (ni
dos
ni ninguna) transición para cada símbolo
posible.
El autómata acepta la cadena de entrada si la
máquina cambia a un estado de aceptación después
de leer el último símbolo de la cadena.
Si después del último símbolo la máquina no queda
en estado de aceptación, se ha rechazado la cadena.
Tuplas delAutómata Finito
Explicación del Diagrama Determinista
Estará caracterizado porque debe estar totalmente
definido:
Para cada estado solo debe salir un arco y solo uno
para cada símbolo (el autómata no puede
determinar la transición en el caso de que haya dos
arcos con el mismo símbolo o no haya ninguno).
Explicación del Diagrama Determinista
Estará caracterizado porque debe estar totalmentedefinido:
Para cada estado solo debe salir un arco y solo uno
para
cada
símbolo
(el
autómata
no
puede
determinar la transición en el caso de que haya dos
arcos con el mismo símbolo o no haya ninguno).
Ejemplo: Definición
El alfabeto S = { a, b, c }
Reconoce la cadena c
La cadena a
Las cadenas que empiezan
por a y acaban en a o
en b y
Las que empiezan por a,...
Un autómata finito es un conjunto de nodos y
aristas que representan trayectorias para generar
una expresión bajo un alfabeto.
Un diagrama de transición es un autómata finito.
Elementos del Autómata Finito
Los estados se identifican dentro de un circulo.
El estado inicial recibe una flecha de transición que
llega de ninguna parte.
Los estado aceptadorespueden identificarse con
doble circulo o con una cruz(igual que signo +) al
lado de ellos.
Las posibles transiciones se indicaran con flechas
que van de un estado a otro, o incluso a sí mismos.
Deben etiquetarse con el símbolo que produce el
cambio de estado.
2
Los Estado del Autómata
Entonces decimos que los estado del autómata
pueden ser:
Estados iniciales
Estados finales llamadosaceptadores
Estados finales no aceptadores
La palabra que va de un estado a otro solo
pertenece al lenguaje si el estado que la recibe es
aceptador.
Y lo contrario, si llega al final hasta un estado no
aceptador, la palabra no pertenece al lenguaje.
3
Ejemplo Gráfico de Autómata Finito
4
Supongamos un Lenguaje X
El lenguaje X es capaz de identificar la siguiente
cadena.
w=aabab
Tratemos
de
identificar
procesos del Autómata.
los
5
Explicación del Automata
Para comenzar estamos en el estado A, podemos
llamarle estado 1.
Hacemos la transición a B cuando leemos el símbolo
a.
Realizamos la siguiente transición de B hacia B
porque leemos nuevamente otro símbolo a.
Para leer b creamos otro estado D al que llegaremos
desde donde estamos que es B.
Para leer elsiguiente símbolo que es a transferimos
de nuevo hacia B.
Luego para leer el siguiente símbolo b, el autómata
regresa hasta D.
1.
2.
3.
4.
5.
6.
6
Ejemplo de Algoritmo para Autómata
7
Autómata Finito Determinista (DFA)
Es un dispositivo que puede estar en un estado de
entre un número finito de los mismos; uno de ellos
será el estado inicial y por lo menos uno será estado
de aceptación.
Tiene un flujo de entrada por el cual llegan los
símbolos de una cadena que pertenecen a un
alfabeto determinado.
8
Autómata Finito Determinista (DFA)
Es un dispositivo que puede estar en un estado de
entre un número finito de los mismos; uno de ellos
será el estado inicial y por lo menos uno será estado
de aceptación.
Tiene un flujo de entrada por el cual llegan los
símbolos de unacadena que pertenecen a un
alfabeto determinado.
9
Analizar el siguiente Ejemplo.
10
Qué podemos deducir de éste ejemplo?
Sobre las transiciones
Sobre los estados
Sobre los símbolos procesados.
11
Porqué Finito, Por qué Determinista?
Porqué finito:
Se refiere que hay un conjunto finito de estados.
Porque determinista:
La palabra determinista es porque el programa no
debetener ambigüedades, es decir, en cada
estado solo se puede dar una y solo una (ni
dos
ni ninguna) transición para cada símbolo
posible.
El autómata acepta la cadena de entrada si la
máquina cambia a un estado de aceptación después
de leer el último símbolo de la cadena.
Si después del último símbolo la máquina no queda
en estado de aceptación, se ha rechazado la cadena.
Tuplas delAutómata Finito
Explicación del Diagrama Determinista
Estará caracterizado porque debe estar totalmente
definido:
Para cada estado solo debe salir un arco y solo uno
para cada símbolo (el autómata no puede
determinar la transición en el caso de que haya dos
arcos con el mismo símbolo o no haya ninguno).
Explicación del Diagrama Determinista
Estará caracterizado porque debe estar totalmentedefinido:
Para cada estado solo debe salir un arco y solo uno
para
cada
símbolo
(el
autómata
no
puede
determinar la transición en el caso de que haya dos
arcos con el mismo símbolo o no haya ninguno).
Ejemplo: Definición
El alfabeto S = { a, b, c }
Reconoce la cadena c
La cadena a
Las cadenas que empiezan
por a y acaban en a o
en b y
Las que empiezan por a,...
Leer documento completo
Regístrate para leer el documento completo.