TAREA 2

Del siguiente grafo obtenga:

Deficinión formal de autómata determinístico

M={K, Σ, δ, S, F}

Σ={a,b}

K={S0,SI, S2}

δ={ ((S0,a), S0 ), ((S0,b), S1), ((S1,a), S2), ((S1,b), S2), ((S2,a), S2), ((S2,b),S1)}

S= {S0}

F= {S2}

Calcule las palabras:

• abbb

[[S0, abbb]] ├ [[S0, bbb]] ├ [[S1, bb]] ├ [[S2,b]] ├ [[S1, ε]]

La palabra NO es aceptada por AFD

• baba

[[S0, baba]] ├ [[S1, aba]] ├ [[S2, ba]] ├ [[S1, a]]├ [[S2, ε]]

La palabra Sí es aceptada por AFD

• bababb

[[S0, bababb]] ├ [[S1, ababb]] ├ [[S2, babb]] ├ [[S1, abb]]├ [[S2, bb]]├ [[S1, b]]├ [[S2, ε]]

La palabra Sí es aceptada por AFD

• abaab

[[S0, abaab]] ├ [[S0, baab]]├ [[S1, aab]]├ [[S2, ab]]├ [[S2, b]]├ [[S1, ε]]

La palabra NO es aceptada por AFD

¿ Cuál es el lenguaje natural de este autómata?

Sea_ la presencia o ausencia de a, b=b, * es la opción de a o b indistintamente, ambas son válidas.

Este autómata acepta palabras con el siguiente formato:

_b*_

repitiéndose periódicamente, así son aceptadas _b*_b*_, etc.
Este susesión no deberá romperse porque en caso contrariola palabra no será aceptada, es decir _b*_b entonces el "ciclo se corta" y faltaría *_ y por tanto no se cumplirá.

El guiónbajo ( _ )representa la ausencia o presencia de la "a" y esto es al inicio y al fianl del autómata ya que en estos dos casos el autómata al consumir a en S1 y S2 permanece en ese estado, así que de cierta manera puede llevarla o no y será aceptada en estos caso.
El asterisco (*) significa que tienes la opción de consumir a o b y es indistinto porque abmas rutas, en este caso específico nos llevan de Si a S2.