Automatas y lenguajes

AUTOMATAS Y LENGUAJE:

Ciencia multidisciplinar que se apoya en que los mismos fenómenos pueden actuar y servir de fundamento en áreas totalmente desconectadas (aparentemente).
• Lainformática teórica:
• se ha desarrollado en base a la confluencia de campos en
• apariencia muy distintos:
• Investigación acerca de Fundamentos Matemáticos,
• Teoría de Máquinas,
•Lingüística,

Pilares de la informática teórica:

• Autómatas / máquinas secuenciales
• Lenguajes y gramáticas
• Máquinas abstractas y algoritmos
Dentro de estos se encuentran:Autómata finito determinista

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata,y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

En un AFD no pueden darse ninguno de estos dos casos:

• Que existan dos transicionesdel tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.
• Un ejemplo interesante deautómatas finitos deterministas son los tries

Autómata finito no determinista

Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitosdeterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera deestos dos casos:

• Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado finalpero con transiciones hacia otros estados.

Construimos una gramática lineal por la derecha G con L(G) = L(M), es decir, genera el mismo lenguaje que el AFD acepta.

Construimos una autómata...