Notas Lenguajes

UNIVERSIDAD MICHOACANA DE SAN NICOLAS DE HIDALGO


FACULTAD DE INGENIERÍA ELECTRICA


CARRERA:

INGENIERIA EN COMPUTACION



NOTAS PARA LA MATERIA DE :

LENGUAJES FORMALES Y AUTOMATASSemestre Agosto 2008/Enero 2009



Autor: Dr. José Antonio Camarena Ibarrola
Profesor de la Materia












INDICE

INTRODUCCIÓN 3
Objetivos : 3
Justificación : 3Usuarios: 3
Definiciones básicas: 4

AUTOMATAS FINITOS 4
Figura 1 Autómata finito del Ejemplo 1 5
AUTOMATAS FINITOS INDETERMINISTAS 6
Figura2. Autómata Finito Indeterminista 7
EQUIVALENCIA ENTREAUTOMATAS FINITOS DETERMINISTAS E INDETERMINSTAS. 7
AF's CON TRANSICIONES 9
EXPRESIONES REGULARES 12
Autómatas Finitos deterministas de dos direcciones: (2DFA) 16
PROPIEDADES DE LOS LENGUAJESREGULARES 20
Algoritmo de minimización 21
Implementación 21
Interfaz de usuario 23
GRAMATICAS LIBRES DEL CONTEXTO 25
FORMA NORMAL DE CHOMSKY (FNC) 27
LA FORMA NORMAL DE GREIBACH (FNG) 28
AUTOMATAS DEPILA 30

MAQUINAS DE TURING 33

Estrategia de solución. 33
Definición formal 37
Código para el simulador de la Máquina de Turing 38
BIBLIOGRAFIA 41















INTRODUCCIÓNLa teoría de autómatas y lenguajes formales son la herramienta matemática que ha permitido el desarrollo de compiladores, interpretes, editores e impresores de código, verificadores de código yotras herramientas CASE (Ingeniería de Software Asistido por computadora de acuerdo a sus siglas en inglés). La Materia de Lenguajes Formales y Autómatas introduce conceptos abstractos un tantocomplicados para los estudiantes de Ingeniería, los libros de texto tradicionales para esta materia han sido escritos por renombrados Matemáticos dedicados al desarrollo de las ciencias de la computación comoJeffrey Ullman o Alfred V. Aho. Estas Notas fueron escritas con el afán de presentar los conceptos de una forma más accesible para estudiantes de Ingeniería con respecto a los Libros Tradicionales...