Datos Generales
Nombre de la asignatura: Lenguajes y Autómatas
Clave de la asignatura: SCB-9324
Horas/teoría: 4
Horas/practica: 0
Créditos: 8

Temario:
Número
Temas
Subtemas
I
 Introducción

1.1 Conjuntos finitos e infinitos
- Alfabeto
- Propiedades de String
- Longitud
- Concatenación
- Lenguaje
1.2 Representación finita del lenguaje
II
 Gramáticas 2.1 Introducción a las gramáticas
2.2 Estructura de las gramáticas
2.3 Clasificación de las gramáticas
- Contexto Sensitivo
- Sensible del contexto
- Libre de contexto
- Estructura de fase
2.4 Representación de gramáticas
- Notación de BNF
- Diagramas sintácticos
III
 Autómatas Finitos 3.1 Autómatas finitos deterministicos (AFD)
3.2 Autómatas finitos no deterministicos (AFND)
3.3 Equivalencia de AFND y AFD
3.4 Propiedades de los lenguajes aceptados por un autómata finito
3.5 Autómatas finitos y expresiones regulares
3.6 Determinación de lenguajes regulares y no regulares
IV
 Autómatas de Push-Down

4.1 Definición
4.2 Lenguajes aceptados por autómata PUSH-DOWN
4.3 PDA deterministico
4.4 PDA y CFL
V Maquina de Turing 5.1 Definicion de maquina de Turing
5.2 Funcionamiento de la maquina de Turing
5.3 Lenguajes aceptados por la maquina de Turing
5.4 Extensiones de la maquina de Turing
5.5 Ejemplo de mayor fuerza de la maquina de Turing
5.6 Maquina de Turing no deterministica
5.7 El problema HALFING para la maquina de Turing
VI Gramáticas y Autómatas 6.1 Lenguajes Regulares
- Teorema de Kleene
- Las aplicaciones del lema de Punping
- El teorema MGHILL
6.2 Lenguajes de contexto libre
- Forma Normal EHUMSKG
- Lema de BARHILL el purping
- Autómata de Push-Down
- Compilador de lenguajes formales
- Lenguaje Brackat

Bibliografia:
1.- Hopcroft, John and Ullman Jefrey. Introduction to Automata's Theor Languages and Computation. Ed. Addison-Wesley.

2.- Harry R. Lewis, Chistos H. Papadimitrion. Elements of the Theory of Computation. Ed. Prentice-Hall.

3.- V. S. Rayward-Smith. A First Course in Formal Language Theory.

4.- Martin D. Davis and Elaine J. Weyuker. Computability, Complexity and Languages. Fundamentals of Theoretical computer Science. Academic Press, Ing. 1983.

Volver