Documentos electronicos

UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA
La Universidad Católica de Loja

MODALIDAD ABIERTA Y A DISTANCIA

ESCUELA DE CIENCIAS DE LA COMPUTACIÓN Guía didáctica

t EORÍA DE AUTÓMATAS Y
LENGUAJES FORMALES
CICLO

6

1. Datos informativos
CARRERA: Ingeniería en Informática
AUTOR: Ing. María Belén Mora Arciniegas.

Reciba asesoría virtual en: www.utpl.edu.ec
MATERIAL DE USO DIDÁCTICOPARA ESTUDIANTES DE LA UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA, PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL POR CUALQUIER MEDIO

18604

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
Guía Didáctica

María Belén Mora Arciniegas. © UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA Diagramación, diseño e impresión: EDITORIAL DE LA UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA Call Center: 593 - 7 - 2588730, Fax: 593- 7 - 2585977 C. P.: 11- 01- 608 www.utpl.edu.ec San Cayetano Alto s/n Loja-Ecuador

Primera edición Primera reimpresión ISBN-978-9942-00-778-0

Reservados todos los derechos conforme a la ley. No está permitida la reproducción total o parcial de esta guía, ni su tratamiento informático, ni la transmisión de ninguna forma o por cualquier medio, ya sea electrónico, mecánico, por fotocopia,por registro u otros métodos, sin el permiso previo y por escrito de los titulares del Copyright. Octubre, 2011

ÍNDICE
ITEM PÁGINA

INTRODUCCION .................................................................................................................................5 OBJETIVOS GENERALES................................................................................................................5 CONTENIDOS ....................................................................................................................................5 BIBLIOGRAFIA ...................................................................................................................................6 ORIENTACIONES PARA EL ESTUDIO.......................................................................................7 PRIMER BIMESTRE CONTENIDOS .................................................................................................................................15 DESARROLLO DEL APRENDIZAJE .......................................................................................17
UNIDAD 1 AUTÓMATAS FINITOS............................................................................. 17 1.1 1.2 1.3 1.4 1.5 1.6 ¿Por qué estudiar la teoría de autómatas? .............................................. 17 Conceptos fundamentales de la teoría de autómatas .......................... 18 Autómatas finitos: Descripción informal de autómata finito .................. 21 Autómata finito determinista ......................................................................21 Autómatas finitos no deterministas............................................................. 25 Autómatas finitos con transiciones – ε ....................................................... 28

Autoevaluación 1: .................................................................................................. 32 UNIDAD 2 LENGUAJES Y EXPRESIONESREGULARES.............................................. 34 2.1 2.2 2.3 Expresiones regulares ................................................................................... 34 Autómatas finitos y expresiones regulares ................................................. 36 Álgebra de las expresiones regulares ........................................................ 38

Autoevaluación 2:.................................................................................................. 42 UNIDAD 3 PROPIEDADES DE LOS LENGUAJES REGULARES ................................... 44 3.1 3.2 3.3 Expresiones regulares ................................................................................... 44 Propiedades de decisión de los lenguajes regulares .............................. 47 Equivalencia y minimización de autómatas...