Book Creator

AUTÓMATAS FINITOS

by MARCO ANTONIO SOTO MATA

Cover

Loading...
Loading...
Rounded Rectangle
Loading...
Soto Mata Marco Antonio
193107154
Lenguajes y Autómatas I
Loading...
AUTÓMATAS FINITOS
Rounded Rectangle
3.1 Conceptos: Definición y Clasificación de Autómata Finito
Rounded Rectangle
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
Definición formal Formalmente:
E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.
3.2 CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.
Rounded Rectangle
Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q0>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones 
1.  A se transforma en AAFD=<QA,T, gA,FA,q0A>', tal que:
Rounded Rectangle
a.    VA=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.
b.    FA={x | }.
c.    gA={<r,x,q> | }.
d.    q0A={q0}
2.    Luego se eliminan de AAFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q0A.
3.3 REPRESENTACIÓN DE ER USANDO AFND.
Rounded Rectangle
ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER→AFND → AFD → ER.
PrevNext