Automatas Finitos y Lenguas regulares

TEMA #1
1. Introducción a los autómatas.

1.1 ¿Por qué estudiar la teoría de autómatas?
-La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase delenguajes formales que son capaces de reconocer.
1.2 – Alfabetos
Conjunto de símbolos
A={a,b,c,d, ….z}

1.3 – Palabras
Concatenación de símbolos pertenecientes a un alfabeto
A={a,b,c,d, ….z}
Casa

1.4 – Lenguajes
Conjunto de palabras formadas sobre un alfabeto
L={alfabeto castellano}
Restricciones (ciertas palabras)

TEMA #2
2. Automatas Finitos y Lenguas regulares




2.1 Definiciones

Unautomata finito nos ayudan a transformar lenguajes.
Tokens: es uncomponente lexico, una cadena de caracteres que tene un significado coherente en n lenguaje.

2.2 Expresiones Regulares (ER): Describe o denota un lenguaje, representa una secuencia de caracteres que consta en un lenguaje.

2.3 Operadores de los (ER):
-» Concatenación
* -» Cero o mas veces
+ -»Una o mas veces
/ -»Operador ‘’o” -» Union

-AFD(Automatas finitos deterministas) No lee vacios “ ø ” , “λ”
2.4 A.F.(automata finito)
-AFND(Automatas finitos no deterministas) Lee “λ”

2.5 Automatas FinitosDeterministas
2.5.1 Tiene
Estados + transiciones
Reconocer construcción (palabra)
Finito




2.5.2 Funciones
Tiene un conjunto de estados(Q,S)
Tiene un conjunto de simbolos (Alfabeto)(X) etc.
Tiene un estado inicial (So,qo)
Tiene un conjunto de estados finales (F) o estados aceptadores
Tiene una funcion transitoria(S)
2.5.2.1 AFD es una quitupla
A = (Q, Σ, δ, q0, F) donde:
Q: es un conjunto finitode estados
Σ, X: es un conjunto finito de símbolos o alfabeto.
δ, S : estado inicial
F: conjunto de estados finales










2.5.3 Ejercicios










2.5.4 Ejercicio2:
ER= a.b
X={a,b}
L={ ab } a b=>EF a
AFD={Q, X, qo, F, S}
Q={ø,1,2}
X={a,b}
qo={ø}
F={3}
S ={ø,a} -> 1
S1 ={1,b} -> 2
2.5.5 Ejercicio3;

ER= a/b
X={a,b} =>EF
L={a,b }
=>EF
AFD={Q, X, qo, F, S}
Q={ø,1,2}
X={a,b}
qo={ø}
F={1,2}
S1={ø,a} -> 1
S2 ={ø,b} -> 2
2.5.6 Ejercico4
ER= a* a
X={a}
L={ λ,a,aa,aaa, … } =>EF

AFD={Q, X, qo, F, S}
Q={ø}
X={a}
qo={ø}
F={ø}
S ={ø,a} -> ø
2.5.7 Ejercicio5:
ER= a+ a
X={a}a
L={ a,aa,aaa, … } =>EF

AFD={Q, X, qo, F, S}
Q={ø}
X={a}
qo={ø}
F={1}
S ={ø,a} -> 1
S={1,a} ->1

2.5.8 Ejercicio6:
ER= a+b+$
X={a,b,$} a b
L={ ab$,aab$ } a b $=>EF a

AFD={Q, X, qo, F, S}
Q={ø,1,2,3}
X={a,b,$}
qo={ø}
F={3}
S ={ø,a} -> 1
S={1,a} ->1
S ={1,b} -> 2
S={2,b} ->2
S={2,$} ->3



2.6 Paso de una ER a un AFN.

2.6.1 Algoritmo de Construcción...