Automatas COL1

Fase 1_Ejercicio 1

Para el autómata de la figura 1.

Figura 1. Autómata Finito propuesto.

Pregunta 1. Enuncie el autómata en notación matemática

Respuesta.

Enunciar un autómata en notación matemática, consiste en expresarlo médiate la tupla que lo caracteriza, que en este caso es una quíntupla, donde se enuncia o relacionan el conjunto de estados del autómata, su alfabeto de entrada, su estado inicial, que pertenece al conjunto de estados del autómata, los estados finales, que son un subconjunto del conjunto de estados del autómata y la función de transición, la cual nos indica un estado del autómata, a partir de un estado anterior y un símbolo del alfabeto de entrada.

La quíntupla que describe o caracteriza matemáticamente al autómata tiene la forma:

M=(K,Σ,s,δ,F)

Bautizando al autómata propuesto como M.

En primer lugar se definirá el conjunto de estados del autómata (K) , como sigue:

k=〖{q〗_0,q_1,q_2,q_3,q_4,q_5}

Siguiendo con el orden de la quíntupla que caracteriza al autómata, se describe ahora el lenguaje de entrada del mismo (Σ), como se muestra a continuación:

Σ^*=(λ,0,1,2)

Se presenta el símbolo del alfabeto de entrada del autómata con estrella de Kleene, pues el alfabeto de símbolos del mismo contiene carácter vacío, de hecho el autómata acepta transiciones a través de este carácter, por tal motivo puede decirse que el autómata es no determinístico.

A continuación se identifican el estado inicial del autómata, marcado con un triángulo o cabeza de flecha en la figura 1. Este estado se identifica en la quíntupla propuesta a través de la letra s.

s=q_0

El estado inicial del autómata pertenece al conjunto de estados de este, es decir

s∈k

q_0∈〖{q〗_0,q_1,q_2,q_3,q_4,q_5}

Los estados finales o de aceptación del autómata, son aquellos marcados en la figura 1 con doble círculo, este conjunto de estados se representa en la quíntupla propuesta a través de la letra F.

Por tanto

F=〖{q〗_0,q_1,q_4,q_5}

El conjunto de estados finales del autómata es un subconjunto del conjunto de todos los estados de este.

F⊆k

〖{q〗_0,q_1,q_4,q_5}⊆〖{q〗_0,q_1,q_2,q_3,q_4,q_5}

Para finalizar con la caracterización matemática del autómata finito de no determinístico de la figura 1, se describe ahora su función de transición, donde debe considerarse que la función de transición, para autómatas finitos no determinísticos por transición vacía es de la siguiente manera:

δ:KX(Σ∪λ)→2^Q

La función de transición presentada anteriormente es una función de transición parcial, la cual permite a los autómatas no determinísticos alcanzar

...