Matematica Discreta
Reynaldo Pastor Oropeza
Dirigido a todos los estudiantes de el curso de Matematica DIscreta en la especialidad de Informatica
Oneymer Castañeda
C.I.: 20.044.920.
Autómatas, gramáticas y lenguajes
Un autómata de estado finito A= (I, O, S, f, g, σ0) es una máquina de estado finito en la que el conjunto de sÃmbolos de salida es {0, 1} y donde el estado actual determina la última salida. Aquellos estados para los que la última salida fue 1 se llaman estados de aceptación.
Dibuje un diagrama de transición de la máquina de estado finito A definida por la tabla. El estado inicial es σ0. Muestre que A es un autómata de estado finito y determine el conjunto de estados de aceptación.
El diagrama de transición se muestra en la figura 12.2.1. Si estamos en el estado σ0, la última salida fue 0. Si estamos en el estado σ1 o σ2, la última salida fue 1; entones A es un autómata de estado finito. Los estados de aceptación son σ1 y σ2.
El ejemplo 12.2.2 muestra que la máquina de estado finito definida por un diagrama de transición será un autómata de estado finito si el conjunto de sÃmbolos de salida es {0, 1} y si, para cada estado σ, todas las aristas que llegan a σ tienen la misma etiqueta de salida. El diagrama de transición de un autómata de estado finito suele dibujarse con los estados de aceptación en cÃrculos dobles y sin los sÃmbolos de salida. Cuando volvemos a dibujar el diagrama de transición de la figura 12.2.1 de esta manera, obtenemos el diagrama de transición de la figura 12.2.2.
Ejercicios
Dibuje el diagrama de transición del autómata de estado finito de la figura 12.2.3 como un diagrama de transición de una máquina de estado finito. Como σ2 es un estado de aceptación, se etiquetan todas sus aristas entrantes con salida 1 (vea la figura 12.2.4). Los estados σ0 y σ1 no son de aceptación, de modo que se etiquetan sus aristas entrantes con salida 0. Se obtiene el diagrama de transición de la figura 12.2.4.
Como alternativa para la definición 12.2.1, se puede considerar un autómata de estado finito A como consistente en
1. Un conjunto finito Ide sÃmbolos de entrada
2. Un conjunto finito Sde estados
3. Una función f del siguiente estado de S×Ien S
4. Un subconjunto Ade Sde estados aceptantes.
5. Un estado inicial σ ∈S.
Si usamos esta caracterización, se escribe A=(I, S, f, A, σ).
En la figura 12.2.5 se ilustra el diagrama de transición del autómata de estado finito A = (I, S, f, A, σ), donde y f está dada por la siguiente tabla:
Si una cadena se alimenta a un autómata de estado finito, terminará ya sea en un estado de aceptación o en un estado de no aceptación. Este estado final determina si el autómata de estado finito acepta la cadena.