PDF de programación - Tema 1: Introducción - Teoría de autómatas y lenguajes formales I

Tema 1: Introducción

Teoría de autómatas y lenguajes formales I

Bibliografía

• Hopcroft, J. E., Motwani, R., y Ullman, J. D.

“Introducción a la Teoría de Autómatas, Lenguajes
y Computación”. Addison Wesley. 2002.
– capítulo 1

• Sudkamp, Thomas A. “Languages and machines :
an introduction to the theory of computer science”.
Addison-Wesley Publishing Company, 1998.
– capítulos 1 y 2

© Manuel Mucientes

Tema 1: Introducción

2

Un poco de historia

• Teoría de autómatas: estudio de “máquinas” o dispositivos

abstractos con capacidad de computación

• Turing (1930): estudio de una máquina abstracta

– determinar la frontera entre lo que se puede y no se puede hacer con

un computador

– máquina de Turing

• 1940, 1950: autómatas finitos
• Finales de los 50: estudio de las gramáticas formales

(Chomsky)

• Cook (1969): separa los problemas que se pueden resolver

eficientemente de los que no (intratables)

© Manuel Mucientes

Tema 1: Introducción

3

Utilidad de la teoría de autómatas

• Autómatas finitos

– Software para el diseño y verificación del comportamiento de

circuitos digitales

– Analizador léxico de un compilador
– Software para explorar texto buscando la aparición de patrones
– Software para comprobar el funcionamiento de un sistema con un
número finito de estados diferentes (protocolos de comunicación,
protocolos de intercambio seguro de información, ...)

© Manuel Mucientes

Tema 1: Introducción

4

Utilidad de la teoría de autómatas (II)

• Gramáticas

– analizador sintáctico (parser)

• Expresiones regulares

– patrones de cadenas

• Autómatas y complejidad

– ¿Qué puede hacer un computador?: decidibilidad
– ¿Qué puede hacer un computador eficientemente?: intratabilidad

© Manuel Mucientes

Tema 1: Introducción

5

Teoría de conjuntos

x ∈ X, x ∉ X

•
• X = {1, 2, 3}, X = {x | x ∈N y x ≤ 3}
• X ⊆ N
• X ∪ Y = {z | z ∈ X o z ∈ Y}
• X ∩ Y = {z | z ∈ X y z ∈ Y}
• X – Y = {z | z ∈ X y z ∉ Y}
• Complemento de X respecto a U:
• Leyes de DeMorgan

–

–

(

YX

YX
∩=∪ )

(

YX

YX
∪=∩ )

XUX

−

=

• Cardinalidad: tamaño de un conjunto, card(X)

– finito
– infinito

• contable o numerable: correspondencia 1 a 1 con los números naturales
•

incontable

© Manuel Mucientes

Tema 1: Introducción

6

Alfabetos y palabras
• Alfabeto: conjunto finito no vacío de símbolos. Σ
• Cadena o palabra: secuencia finita de símbolos pertenecientes

a un alfabeto.
– cadena vacía: ∈, λ, ε
– Longitud de la cadena: |w|

• Potencias de un alfabeto: conjunto de todas las cadenas de

una cierta longitud que se pueden formar con un alfabeto
– Σk
– Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪ ...
– Σ* = Σ+ ∪ {∈}

© Manuel Mucientes

Tema 1: Introducción

7

Operaciones con palabras

• Concatenación de cadenas: sean x e y dos cadenas.

xy es la concatenación de x e y

• Potencia: la potencia i-ésima de una palabra x, xi, se

forma por la concatenación i veces de x

• Reflexión: si la palabra x está formada por los
símbolos A1...An, entonces la palabra inversa de x, x-1,
se forma invirtiendo el orden de los símbolos en la
palabra. x-1 = An...A2A1

© Manuel Mucientes

Tema 1: Introducción

8

Lenguajes

• Dado un alfabeto Σ, cualquier L ⊆ Σ* será un lenguaje de Σ
• El alfabeto sobre el que se define el lenguaje debe ser

finito, aunque el lenguaje puede tener un número infinito de
cadenas
• Ejemplos:

– Lenguaje vacío: ∅
– Lenguaje que contiene únicamente la cadena vacía: {∈}
– L = {w | w contiene el mismo número de ceros y unos}
– L = {0n1n | n ≥ 1}
– L = {aibjck | j = i+k e i, j, k > 0}

© Manuel Mucientes

Tema 1: Introducción

9

Operaciones con lenguajes

• Unión: L1 ∪ L2, contendrá todas

las palabras que

pertenezcan a cualquiera de ellos
Intersección: L1 ∩ L2, contendrá todas las palabras que
pertenezcan a ambos

•

- L2, contendrá todas

las palabras que

pertenezcan a L1 y no a L2

• Resta: L1
• Concatenación: L1 . L2, contendrá todas las palabras que
se puedan formar por la concatenación de una palabra de
L1 y otra de L2

• Potencia: la potencia i-ésima de un lenguaje es la

concatenación i veces del lenguaje consigo mismo
– Σ*: cierre o clausura
– Σ+: clausura positiva

• Reflexión: está formada por la aplicación de la reflexión a
cada una de las palabras del lenguaje. Se representa por L-

© Manuel Mucientes

Tema 1: Introducción

10

Gramáticas y autómatas

• Una gramática establece la estructura de un lenguaje, es decir, las
sentencias que lo forman, proporcionando las formas válidas en que se
pueden combinar los símbolos del alfabeto

• Chomsky: clasificación de las gramáticas

– G0 o de Tipo 0: gramáticas sin restricciones
– G1 o de Tipo 1: gramáticas sensibles al contexto
– G2 o de Tipo 2: gramáticas independientes del contexto
– G3 o de Tipo 3: gramáticas regulares

• G3⊆G2⊆G1⊆G0
• Cada gramática es capaz de generar un tipo de lenguaje

– El lenguaje L será de tipo “i” (i=0,1,2,3) si existe una gramática de tipo “i” capaz

de generar o describir dicho lenguaje

• Máquina abstracta o autómata: dispositivo teórico capaz de recibir y
transmitir información. Dada una cadena de símbolos presentados a su
entrada, produce una cadena de símbolos a la salida, en función de dichas
entradas y los estados internos por los que transita la máquina.

© Manuel Mucientes

Tema 1: Introducción

11

Lenguajes, gramáticas y autómatas

Equivale

Gramática

Máquina

Describe
Genera

Reconoce
Genera

Lenguaje

Gramática

Lenguaje

Máquina

Tipo 0: sin restricciones

Sin restricciones

Máquina de Turing (MT)

Tipo 1: sensible al contexto

Sensible al contexto

Tipo 2: contexto libre o
independiente del contexto
Tipo 3: regular

Contexto libre o
independiente del contexto
Regular

Autómata Linealmente
Acotado (ALA)
Autómata con Pila (AP)

Autómata Finito (AF)

© Manuel Mucientes

Tema 1: Introducción

12