Automatas

Teor´ de Aut´matas y Lenguajes Formales ıa o
Laura M. Castro Souto Primer Cuatrimestre Curso 2000/2001

2

´ Indice de cuadros

3

4

´ INDICE DE CUADROS

Cap´ ıtulo 0 Introducci´n o
En la asignatura de Teor´ de Aut´matas y lenguajes formales vamos a tratar ıa o los “cimientos”, los fundamentos te´ricos de todo lo que tiene que ver con la inform´tica o a y los computadores. Noen vano a este campo se le denomina en ocasiones Inform´tica a Te´rica. o Estudiaremos los lenguajes formales, lenguajes con una estructura formal, matem´a tica, con unas reglas que nos permitir´n usarlos de forma correcta. Veremos esas directrices a y posteriormente qu´ resultar´ correcto y qu´ no ateni´ndonos a ellas. e ıa e e Construiremos aut´matas para poner en pr´ctica las posibilidades delos lenguajes. o a Enlazando ambos, las gram´ticas, asociadas tanto a los lenguajes como a los aut´a o matas. lenguajes formales l. regulares l. indep. del contexto l. recursivos l. recursivamente enumerables ´ automatas a. finitos a. de pila ´ maquinas de turing ´ gramaticas g. regulares g. indep. del contexto funciones mi-recursivas ´ λ-calculo problemas

Las gram´ticas regulares sonfundamentales para el estudio de los compiladores, puesto a que permiten hacer de forma c´moda el an´lisis l´xico. Las gram´ticas independientes del o a e a contexto, por su parte, nos facilitan el an´lisis sint´ctico. a a En la segunda parte de la asignatura veremos el concepto fundamental que constituyen las M´quinas de Turing, un modelo matem´tico de toda la teor´ de la computaci´n. En su a a ıa ocontexto, las funciones mi-recursivas, en las que se basan todos los lenguajes imperativos, y su equivalente base de los lenguajes de programaci´n funcional, el λ-c´lculo. o a Por ultimo, nos ocuparemos de los muchos problemas que se pueden resolver y tambi´n ´ e de los que no se pueden resolver, que son a´n muchos m´s. u a

5

6

´ CAP´ ITULO 0. INTRODUCCION

Cap´ ıtulo 1 Alfabetos y lenguajes1.1. Alfabetos, palabras y lenguajes

Llamamos alfabeto, y lo representamos , a un conjunto finito de s´ ımbolos que utilizamos para construir frases, programas, representaciones de n´meros. . . u Una palabra (o cadena) es una secuencia finita de s´ ımbolos de un alfabeto. A las palabras se les puede dar significado e interpretaci´n como s´ o ımbolos. Cada s´ ımbolo puede a su vez serinterpretado como una palabra. Son palabras: pan, pppban,. . . Ejemplo: = {a, b, 1, 2} Palabras: ab, ba, b12, ba2abbb

Representaremos por ε (a veces por λ) el concepto de palabra vac´ que es impresıa, cindible y simboliza la palabra que no tiene ning´n s´ u ımbolo. Se denomina cierre de sigma ´ sigma estrella, o que se pueden construir a partir de un alfabeto. Ejemplo: = {1, 2} ;
∗ ∗

, al conjunto detodas las palabras

= {ε, 1, 2, 11, 12, 21, 22, 111, . . . }

La longitud |ω|1 de una palabra es el n´mero de s´ u ımbolos del alfabeto que contiene. Por ejemplo, |21221| = 5. Concatenar dos palabras es poner una a continuaci´n de la otra: o
∗

· −→ (w, z) wz ε (neutro) ×
∗

∗

Se definen las potencias de una palabra: ωn = ε si n = 0 n−1 ωω si n > 0

Usaremos tambi´n otros conceptossimples y sencillos ampliamente conocidos, como e prefijo, sufijo, subcadena,. . .
1 Por convenio, utilizaremos las letras a, b, c,. . . y los n´meros 1, 2, 3,. . . para representar s´ u ımbolos y las letras u, v, w,. . . para representar palabras.

7

8

CAP´ ITULO 1. ALFABETOS Y LENGUAJES La inversa ´ traspuesta de una palabra es: o  si ω = ε  ω I a∈ ω =  y I a si ω = ay, con y∈

∗Lenguajes Dado un alfabeto cualquiera , hemos definido ∗ . A partir de esto, decimos que un lenguaje A es un subconjunto de ∗ , A ⊆ ∗ . Tenemos ℵ1 lenguajes. Sobre un mismo alfabeto se pueden tener diferentes lenguajes. Un lenguaje importante es el lenguaje vac´ ∅. Tambi´n es un lenguaje, y diferente, el ıo, e lenguaje {ε}. Concatenaci´n de lenguajes: o A·B = Potencia de un lenguaje: An = Otras...