Automatas

Introducción a la Lógica y la Computación
Parte III: Lenguajes y Autómatas

Autores: Alejandro Tiraboschi y Pedro Sánchez Terraf

Contenidos
1 Introducción 2 Lenguajes y Autómatas 2.1 Cadenas, alfabetos y lenguajes . . 2.2 Sistemas de estados finitos . . . . 2.3 Autómatas finitos . . . . . . . . . 2.4 Autómatas no determinísticos . . . 2.4.1 Formalización de los NFA 2.5 Expresiones regulares. . . . . . . 2.5.1 Teorema de Kleene . . . . 2.6 Pumping Lemma . . . . . . . . . 2.7 Ejercicios . . . . . . . . . . . . . 1 3 3 3 5 9 12 16 19 26 28 36 37 40 43 45 50

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

3 Gramáticas 3.1 Definiciones básicas y ejemplos . . . . . . .. . . . . . . . . . . . . . . . . . . . . 3.2 Formas normales de Chomsky y Greibach . . . . . . . . . . . . . . . . . . . . . . . 3.3 Gramáticas regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Autómatas con pila 4.1 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Introducción
En esta parte de la materia vamos aempezar a estudiar modelos de computación. Es decir, modelos teóricos que aproximan el comportamiento de una computadora. Este tema se verá en más detalle en otras materias más avanzadas, cuando se estudien las Máquinas de Turing que nos servirán para definir exactamente que significa computar y cuales son sus límites. En esta materia estudiaremos un tipo de máquinas más simples que las máquinas de Turingque se llaman autómatas, y veremos que existe una relación muy fuerte entre modelos de computación y lenguajes formales. Una computadora que resuelve un problema mediante algún algoritmo puede verse en forma abstracta como “hablando el lenguaje” {(input1 ,output1 ), . . . , (inputn ,outputn ), . . . }. Notar que podemos pensar que este lenguaje es un conjunto de cadenas {input1 #output1 , . . . ,inputn #outputn , . . . }, donde 1

# es algún símbolo que no apareza en los inputs o los outputs. Por ejemplo la funcion f (x) = x3 puede asociarse con el conjunto de cadenas {0#0, 1#1, 2#8, 3#9, . . . }. Es por esto que una forma de estudiar las cosas que una computadora puede realmente computar, es investigando que lenguajes que distintos tipos de máquinas pueden producir. Miremos un pocomas en detalle a que nos referimos cuando decimos ‘máquinas’. De forma muy abstracta, podemos representar una computadora simplemente con el siguiente diagrama:

CPU

Memoria

donde sólo diferenciamos una unidad con capacidad de procesamiento (el CPU) de una unidad con capacidad de almacenamiento (la memoria). Nos va a interesar particularmente distinguir distintos tipos de memoria:Memoria Temporaria Memoria Input CPU Memoria Output Memoria de Programa
No nos interesa, en este momento, definir más precisamente cuales son las diferencias entre los distintos tipos de memoria, y nos alcanza con el siguiente ejemplo:

Memoria Temporaria
z := 2*2 z := 2*4

f(x) = x3 Memoria Input
x := 2

CPU

Memoria Output
x := 8

z := x*x; z := x*z; x := z

Memoria de Programa
Ahorasí, vamos a considerar que las ‘máquinas’ que vamos a estudiar siempre tienen memoria input, memoria output y memoria de programa (esto simplemente quiere decir que toman un input, producen un output y siguen algún tipo de programa), pero difieren en el tipo de memoria temporaria que pueden tener: • Autómatas de Estados Finitos (Finite State Automata): no tienen ningún tipo de memoria temporaria....