Tema1

Vista previa del material en texto

Teoría de la Computación para Ingeniería de Sistemas: un
enfoque práctico
Prof. Hilda Contreras
15 de abril de 2012
2
Índice general
1. Introducción 5
1.1. Marco histórico de la teoría de la computación . . . . . . . . . . . . . . . . . . 5
1.2. Conceptos básicos: Alfabeto, Palabra o Cadena, Lenguaje y Problema . . . . . 7
1.3. Jerarquía de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Los problemas en la Teoría de la Computación . . . . . . . . . . . . . . . . . . 10
1.5. Preguntas y respuestas, ejercicios resueltos y propuestos . . . . . . . . . . . . . 11
2. Lenguajes Regulares y autómatas �nitos 15
2.1. Autómatas de estados �nitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1. Autómatas �nitos determinista (AFD) . . . . . . . . . . . . . . . . . . . 15
2.1.2. Autómatas �nitos no determinista (AFND) . . . . . . . . . . . . . . . . 19
2.1.3. Autómatas �nitos no determinista con transiciones nulas (AFND-λ) . . 23
2.1.4. Herramientas, implementación y uso de Lenguajes regulares . . . . . . . 29
2.1.5. Preguntas y respuestas, ejercicios resueltos y propuestos . . . . . . . . . 32
3
4 ÍNDICE GENERAL
Capítulo 1
Introducción
La teoría de la Computación es un poco más antigua que las computadoras electrónicas.
Uno de sus pioneros, Alan Turing, pudo anticipar el poder de las computadoras a través de
un modelo conceptual en 1936. Otras disciplinas como la matemática, �losofía, lingüística,
biología e ingeniería eléctrica intervienen para completar sus teorías. Las teorías de bases son
dos: Teoría de Autómatas y Teoría de los Lenguajes Formales. En general, la Teoría de la
Computación facilita la comprensión de muchas áreas de la ciencia de la computación (como
los compiladores), además:
1. Se utiliza en el diseño y construcción de aplicaciones importantes de software y hardware.
2. Ayuda a comprender que esperar del software.
3. Permite deducir si es posible resolver un problema (determinar los límites de la compu-
tación).
Además, la comprensión de estas teorías representa en la práctica un conjunto de herramientas
muy útiles como alternativas simples y e�cientes para resolver problemas.
1.1. Marco histórico de la teoría de la computación
Esta teoría surge a partir de importantes antecedentes del área de las matemáticas, la cual
estuvo en una profunda cirsis a �nales del siglo XIX y primera mitad del XX. La lógica y
las matemáticas trabajaron juntas en la formalización de la ciencia de la computación, los
siguientes hechos son los mas resaltantes:
Entre 1910 y 1923, Bertrand Russell elabora el "Principia Matemática"presentando la
relación entre la lógica y la matemática pura.
En 1928, el matemático alemán David Hillbert, presenta a sus colegas como reto demos-
trar tres proposiciones de gran generalidad sobre su ciencia:
• La matemáticas son completas.
• Las matemáticas son consistentes.
• Las matemáticas son decidibles.
5
6 CAPÍTULO 1. INTRODUCCIÓN
En 1928, el matemático Ackermann presenta también el problema de la decisión en un
estudio sobre la lógica de primer orden.
En 1930, el matemático checo Kurt Gödel prueba que las matemáticas no pueden ser
completas y consistentes al mismo tiempo (teorema de la Incompletitud).
En 1936, el matemático americano Alonzo Church responde negativamente en un artículo
al tercer problema propuesto por Hillbert, el problema decisorio (Teorema de Church y
λ-cálculo).
En ese mismo año 1936, el matemático inglés Alan Turing da una respuesta también
negativa a esa tercera cuestión, sus resultados son más consistentes que los obtenidos
por Church. La demostración de Turing se basa en principios completamente básicos
y elementales. Turing enuncia el problema de decisión de la siguiente forma: "Buscar
un algoritmo para determinar si una conclusión particular puede derivarse de ciertas
premisas con el uso de reglas de prueba". Da una noción precisa del concepto de algoritmo,
como aquello que pueda ser realizado por una máquina abstracta, la Máquina de Turing.
De este modo, Alan Turing con su máquina universal capaz de realizar el trabajo de
cualquier otra máquina, mediante la lectura de su descripción en una cinta, delinea el
diseño de un computardor.
En 1969, S. Cook extiende el estudio de Tuning. Cook separa aquellos problemas que
pueden ser solucionados de aquellos que en principio pueden ser solucionados pero que
en la práctica toman demasiados recursos (Complejidad computacional).
En 1937, Claude Shannon presenta su tesis de licenciatura en el MIT, estableciendo el
paralelismo entre la lógica de Boole y los circuitos de transmisión.
En 1943, McCulloch-Pitts desarrolla unas máquinas simples, en cuanto su funcionamien-
to, que fueron conocidas como autómatas �nitos de actividad nerviosa, para modelar el
funcionamiento de una neurona biológica.
En 1956, Moore publica el primer estudio riguroso sobre autómatas. Con anterioridad,
debido al desarrollo de los primeros computadores, se habían estudiado diversos métodos
para la síntesis de circuitos secuenciales (Hu�man en 1954 y Mealy en 1955). En los años
60 es donde se realizan la mayor parte de trabajos sobre la teoría de los autómatas �nitos.
En 1956, N. Chomsky comienza el estudio formal de las gramáticas (como generadoras
de lenguajes). Formaliza matemáticamente los conceptos de gramática generativa o re-
glas para la construcción las frases de un lenguaje. Enuncia la teoría sobre el origen y la
naturaleza de los lenguajes naturales. Estas herramientas fueron empleadas para la for-
malización de los lenguajes de computación: Teoría de los Lenguaje Formales. A �nales
de los años 50 se relacionan los autómatas, las gramáticas y los lenguajes (Jerarquía de
Chomsky).
1.2. CONCEPTOS BÁSICOS: ALFABETO, PALABRAO CADENA, LENGUAJE Y PROBLEMA7
1.2. Conceptos básicos: Alfabeto, Palabra o Cadena, Lenguaje
y Problema
La Teoría de la Computación puede entenderse como un paradigma o un enfoque para
resolver problemas. Este paradigma tiene los siguientes conceptos básicos sobre los cuales se
fundamenta: Alfabeto, Palabra o Cadena, Lenguaje y Problema. Para todas estas de�niciones
debe tenerse presente primero el concepto de un Conjunto, como la estructura que las soporta.
Conjunto
Colección (no importa el orden) de objetos (elementos del mismo tipo) sin repetición.
Existen 2 (dos) tipos de representación de los conjuntos:
Por Extensión, se enumeran todos sus elementos, por ejemplo: {0, 1}
Por Comprensión, se de�ne de manera formal las características de sus elementos,
por ejemplo: { i | Para todo j entero i = 2j }
El conjunto vacío se representa así: ϕ. La pertenencia de un elemento a un conjunto: A
= {0, 1, 2} y 1 ϵ A o también se escribe 1 en A. 1
El subconjunto: A ⊆ B signi�ca que todo elemento de A esta en B. Si A ⊆ B y A ̸= B
entonces escribimos A ( B (subconjunto propio).
Operadores sobre conjuntos:
Unión: A
∪
B = {x | x en A o x en B}
Intersección: A
∩
B = {x | x en A y x en B}
Diferencia: A - B = {x | x en A y x no está en B}
Conjunto Producto ó Producto Cartesiano: A × B {(x,z) | x en A y z en B}. Si A
tiene n elementos y B tiene m elementos entonces A × B tiene n × m elementos y
A∗ tiene 2n elementos.
Conjunto de Potencias 2A ó A∗, es el conjunto de todos los subconjuntos de A. Tam-
bién A∗ es denominado Clausura de Kleene de A. Las de�niciones formales son: A∗
=
∪|A|
i=0A
i y A+ =
∪|A|
i=1A
i (clausura positiva que no incluye al conjunto vacío).
Donde Ai representa todos los subconjuntos de A con i elementos.
Ejemplo:
Dados los conjuntos A = {1,2} y B = {2,3}, se realizan las siguientes operaciones sobre
conjuntos:
A
∪
B = {1, 2, 3}
A
∩
B = {2}
A - B = {1}
A × B = {(1,2),(1,3),(2,2),(2,3)}
2A = A∗ = {ϕ,{1},{2},{1,2}}
1 Nota: ϵ es un símbolo que puede ser utilizado por algunos autores para denotar a la cadena vacía.
8 CAPÍTULO 1. INTRODUCCIÓN
En la Teoría de la Computación se visualizan las entradas, salidas y procesos de un dominio
de aplicación como un tipo de problema particular: resolver la pertenenciade un elemento a
un conjunto. El problema, los elementos y el tipo de conjunto que se van a utilizar se de�nen
en base a los siguientes conceptos básicos:
1. Alfabeto: Denotado con Σ (sigma). Conjunto �nito de símbolos no vacíos. Por ejemplo:
Alfabeto binario Σ = {0,1}. Símbolo: es una entidad abstracta que no se de�ne, por
ejemplo números, letras, etc.
2. Cadena (Palabra): secuencia �nita de símbolos pertenecientes a un alfabeto (yuxtapues-
tos = uno detrás del otro). Por ejemplo: Cadena binaria "0111001". Sobre las cadenas se
de�nen:
a) Cadena Vacía λ (lambda): contiene cero (0) símbolos, puede construirse a partir de
cualquier alfabeto.
b) Longitud de una Cadena: número de posiciones de la cadena ocupadas por símbo-
los del alfabeto. Denotado con el pipe |, por ejemplo para el alfabeto binario, las
longuitudes de las siguientes cadenas son |01101|= 5 y |λ|=0
c) Concatenación de Cadenas : x y y son cadenas entonces xy denota la concatenación.
Por ejemplo: x = 011 y = 1110, la concatenación de xy = "0111110"
d) Potencias de un Alfabeto: Conjunto de todas las cadenas formadas a partir de un
alfabeto de cierta longitud.
Σk Cadenas de longitud k formadas por símbolos del alfabeto Σ. Para el alfabeto
binario Σ = {0,1}, Σ2 = {00, 11, 10, 01}
Σ∗ Conjunto de todas las cadenas formadas por símbolos del alfabeto Σ. Se
de�ne por Σ∗ = Σ0
∪
Σi. Donde Σ0 = {λ} y Σi =
∪∞
i=1Σ
i. Además se denota
el Σ+ = Σ∗ − {λ}
e) Su�jo, Pre�jo: cualquier cadena al �nal o comienzo respectivamente de la cadena.
Por ejemplo para la cadena w=abca, formada de Σ = {a, b, c}, se tiene:
Los pre�jos de w= λ, a, ab, abc, abca
Los su�jos de w= λ, a, ca, bca, abca
f ) Pre�jo (Su�jo) propio, es cualquier Pre�jo (Su�jo) que no sea la misma cadena.
3. Lenguaje: Conjunto de cadenas de símbolos del mismo alfabeto. El lenguaje formado
por toda las cadenas posibles de un alfabeto se denota por Σ∗ (Sigma asterisco).
ϕ es el lenguaje vacío, es un lenguaje para cualquier alfabeto.
{λ} es un lenguaje formado por la cadena vacía. Es un lenguaje para cualquier
alfabeto Σ.
Por Ejemplo: Σ1 = {0, 1}, Σ2 = {00, 1}
2
Σ∗1 = {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ... }
Σ∗2 = {λ, 00, 1, 001, 100, 0000, 11, 00001, 00100, 10000, 1001, 0011, 111, 000000,...
}
Las cadenas formadas con Σ2 al aplicarle la cardinalidad: |001| = 2 y |1100| = 3
1.3. JERARQUÍA DE CHOMSKY 9
Figura 1.1: De�nición de Problema en la Teoría de la Computación
4. Problema: consiste en determinar la pertenencia de una cadena sobre un lenguaje. Este
tipo de problema es llamado un Problema de Decisión: función con salida binaria (si,
no) aplicada sobre conjuntos. Por ejemplo ver �gura 1.1: se de�ne un conjunto A con
todas las posibles respuestas y un conjunto B que es subconjunto de A cuyos elementos
son positivos (salida si, que pertenecn a B). Expresado en términos de la teoría de la
computación, si Σ es un alfabeto y L es un lenguaje de Σ∗, entonces el problema sobre
L es el siguiente:
Dada una cadena w que pertenece a Σ∗, decidir si ¾w pertenece o no a L?
1.3. Jerarquía de Chomsky
Noan Chomsky en los años 50, fue el creador de una jerarquía de lenguajes según las
gramáticas que los generan. Esta gramática está organizada en base al poder generativo formal
de la gramática y donde se destaca 4 tipos de gramáticas (denominados tipo 0, tipo 1, tipo 2
y tipo 3), cada una de�nida por la clase de reglas que contiene. El cuadro 1.1, muestra una
jerarquía implicativa, de modo que los lenguajes de�nidos por gramáticas del tipo-i incluyen
los lenguajes del tipo-(i+1). Dicho de otra forma: Tipo 3 ⊂ Tipo 2 ⊂ Tipo 1 ⊂ Tipo 0. Por
tanto las gramáticas de tipo 0 son las más poderosas y las de tipo 3 las más restringidas.
La Teoría de Autómatas y la Teoría de las Gramáticas formales tienen una estructura similar
aunque traten de aspectos diferentes - procedimientos y gramáticas, respectivamente-. Las
gramáticas generan un tipo de lenguaje y los autómatas reconocen un tipo de lenguaje, es
decir el punto de conexión son los lenguajes. Esta es la razón por la cual se utiliza la jerarquía
de Chomsky en la solución de problemas: un problema consiste en determinar si una cadena
pertenece a un lenguaje, entonces si se conoce el tipo de lenguaje se puede determinar con que
máquina reconocerlo o con cual tipo de gramática generarlo.
2Los símbolos del alfabeto pueden ser de diferentes tamaños
10 CAPÍTULO 1. INTRODUCCIÓN
Cuadro 1.1: Jerarquía de Chomsky
Tipo Lenguaje Máquina Gramática G = (V,T,P,S)
0 Recursivamente
enumerable
Máquina de
Turing
Gramática sin restricciones α → β (α, β
en (V
∪
T )∗, α contiene una variable)
1 Dependiente del
Contexto
Autómata
linealmente
acotado
Gramática sensible al contexto α → β (α,
β en (V
∪
T )∗, α contiene una variable,
|β| ≥ |α|)
2 Independiente
del Contexto
Autómata de
Pila
Gramática libre de contexto A → α (A en
V y α en (V
∪
T)∗)
3 Lenguaje Regu-
lar
Autómata �-
nito
Gramática Regular A → aB, A → a, (A,B
en V y a en T)
1.4. Los problemas en la Teoría de la Computación
Teoría de la Computación trata de una teoría o formalismo general, la idea es aplicarla
sobre todos los problemas que se pueden calcular en cualquier máquina. La teoría usa modelos
de máquinas abstractas, pues no tendría sentido usar las máquinas reales que cambian cons-
tantemente en el tiempo y que además son diferentes y complejas. Entonces ¾qué sucede con
los problemas?, ¾los problemas también son abstractos?.
Lo que se pretende calcular, es decir el Problema o Cálculo, puede ser de cualquier tipo, na-
turaleza y condición. Los que han programado han podido resolver, de muchas formas, con
un lenguaje de programación múltiples tipos de problemas. Además hay muchos lenguajes de
programación e incluso algunos especí�cos para ciertas características de los problemas. Se
sabe que los problemas no son iguales, entonces, ¾cómo esta Teoría puede generalizar a todos
los problemas para aplicar sus reglas y sus modelos abstractos?. Bien, es lo primero que hay
que entender, lo que hace la Teoría de la Computación es formalizar un solo tipo de problema,
por tanto se debe convertir, transformar o reducir cualquier problema a lo que se llaman un
"problema de decisión".
Un problema de decisión es un problema que puede dar una respuesta positiva o negativa (si o
no). Un problema de decisión, en términos matemáticos, es equivalente a decidir si un elemento
pertenece o no a un conjunto dado. El conjunto equivalente al problema esta formado por los
elementos para el cual la respuesta es positiva (si). La �gura 1.2 muestra el esquema general
de los problemas.
El Entscheidungsproblem [1] (problema de decisión en alemán) se de�ne como "dada una
Figura 1.2: Problema de decisión en Teoría de la Computación
frase del cálculo de predicados de primer orden, decidir si ella es un teorema", es el problema de
1.5. PREGUNTAS Y RESPUESTAS, EJERCICIOS RESUELTOS Y PROPUESTOS 11
decisión que motivó a Turing y a Church a dar origen a la Teoría de la Computación en 1936.
Un ejemplo típico de este tipo de problema es la siguiente pregunta: ¾Es primo un número
entero dado?, y una instancia de este problema sería: ¾Es 17 un número primo?. Se trata de
entender al 17 como un elemento del conjunto de todos los números enteros y se quiere saber
si pertenece al conjunto de los números primos.
Lo anterior lleva a la pregunta de si realmente es posible reducir o rede�nir todos los problemas
a la forma de un problema de decisión. Para lo cual le sugiero platearse ejemplos e investigar
esta posibilidad, pues es en base a esta generalización de problemas sobre la cual funciona la
Teoría de la Computación. Esto puede parecer una desventaja, como lo menciona Hopcroft [2]:
. . . Un aspecto potencialmente poco satisfactorio de esta de�nición de problema es
que normalmente no se piensa en los problemas como cuestiones de decisión (¾es
o no verdadero lo siguiente?) sino como solicitudes para calcular o transformar
algunos valores de entrada (encontrar la mejor forma para realizar esta tarea). . .
Sin embargo, según la computabilidad y complejidad las soluciones al problema de decisión y
al problema original se diferencian a lo sumo por un factor lineal y se puede decir que vale la
pena esta generalización de los problemas a cambio del formalismo que necesita la Ciencia de
la Computación.
Esta teoría de la computación entonces va a de�nir los problemas en función de un lenguaje.
Justamente, el cuadro 1.1 muestra la jerarquía de Chomsky en donde se relacionan los tipos de
lenguajes (problemas) con el tipo de máquina (modelo) que reconoce cadenas que pertenecen a
cada tipo y a la gramática (modelo) que genera las cadenas que pertenecen al tipo de lenguaje.
Dicha jerarquía estable una relación inclusiva entre los lenguajes, asi, el lenguaje Tipo 3 ⊆
Tipo 2 ⊆ Tipo 1 ⊆ Tipo 0. Esto quiere decir que los lenguajes Tipo 0 son el tipo de lenguaje
que abarca a todos los que se pueden resolver a través de una Máquina de Turing (la más
poderosa).
1.5. Preguntas y respuestas, ejercicios resueltos y propuestos
Preguntas y respuestas
1. ¾Qué es una teoría? [3] Dentro del proceso de producción cientí�ca: Una Teoría es un
conjunto de medios de representación conceptual y simbólica (explicativo de los hechos),
que tiene además un conjunto de reglas de inferencia que permiten la previsión de los
datos de hecho.
2. ¾Qué es una máquina abstracta? Es una máquina que no existe físicamente, pero que
ejecuta instrucciones sobre una entrada y produce una salida, habitualmente se han em-
pleado en el estudio de la computabilidad. Ejemplos: Autómatas Finitos, Autómatas a
Pila, Autómatas linealmente acotados y Máquina de Turing. La computadora que utili-
zamos es compleja, cambia con el tiempo, por tanto una teoría basada en especi�caciones
de hardware no sería muy útil, por tanto los Modelos de Computación están basados en
máquinas abstractas. (matemática).
3. ¾Qué es el poder de una máquina abstracta?, ¾qué signi�ca que una máquina sea más
poderosa que otra?. En el contexto de la Teoría de la Computación, una máquina es
12 CAPÍTULO 1. INTRODUCCIÓN
poderosa en la medida que soluciona problemas sin importar como lo hace (no importa
la e�ciencia en tiempo y recursos, sino su efectividad en lograr resolver el problema). En
los términos del paradigma, si una máquina reconce lenguajes más complejos será más
podedora, según la Jerarquía de Chomsky la máquina que reconoce el lenguaje tipo 0 es
la más poderosa.
Ejercicios resueltos
1. Diferencia entre el operador clausura de Kleene aplicado sobre un conjunto y sobre un
alfabeto. Por ejemplo: El conjunto A = {a,b} cuál es el A* y para el alfabeto B = {a,b}
cuál es B*.
La diferencia se debe a que el operador estrella o clausura de Kleene es polimór�co.
Aunque A y B son el mismo conjunto, se interpretan de forma diferente para el operador.
En el caso de A es un conjunto de elementos y A* es el conjunto de todos sus subconjuntos,
A es �nito y A* también, A* = {ϕ, {a}, {b}, {a, b}}. En el caso de B, es interpretado
como un alfabeto, es decir un conjunto �nito de símbolos. Aplicando el mismo operador
a B nos dá un conjunto in�nito, B* = {λ, a, b, aa, ab, ba, bb, aaa, aab, aba, ... } (se
está formando el conjunto de todas las cadenas, incluyendo la cadena vacía, que se puede
formar con el alfabeto B).
2. Considere el proceso de compilación de un programa escrito en un lenguaje de pro-
gramación. Identi�que el alfabeto, cadena, lenguaje y problema según la Teoría de la
Computación.
El problema de la compilación de un programa escrito en algún lenguaje de programación
puede ser visto a través del paradigam de lenguajes formales que contiene la Teoría de
la Computación. El compilador no es más que un sistema que es capaz de ver si una en-
trada (el código fuente) esta bien escrito y sigue las reglas del lenguaje de programación
que está reconociendo. Es decir, el compilador es una máquina reconocedora de textos
(códigos fuente) que pertenecen al conjunto de todos los códigos escritos en un lenguaje
de programación. De esta forma se de�nen:
El alfabeto Σ: es el conjunto de símbolos que puede escribirse en un teclado de
computador con el cual puede escribirse texto (caracteres alfanuméricos, caracteres
especiales, espacio, etc.).
Cadena de entrada w: La entrada del compilador visto como una máquina reco-
nocedora, no es más que cualquier texto que podamos escribir con el teclado del
computador (es decir con Σ). Cada cadena w se puede generar concatenando ele-
mentos de Σ, de esta maneras tenemos in�nitas cadenas (textos)y entonces Σ∗ es
in�nito.
El lenguaje L: es el subconjunto de Σ∗ formado por las cadenas (texto) que siguen
las reglas de un lenguaje de programación especí�co. El compilador reconoce un
lenguaje L in�nito pues las reglas de un lenguaje de programación (aunque son
�nitas) permiten escribir in�nitos programas que formarían parte de L.
El problema P: El compilador resuelve un problema de decisión al determinar si un
texto de entrada compila o no. Decir que un texto compila signi�ca que pertenece
al lenguaje L de todas los posibles e in�nitos códigos que pueden escribirse en
1.5. PREGUNTAS Y RESPUESTAS, EJERCICIOS RESUELTOS Y PROPUESTOS 13
el lenguaje de programación. Decir que un texto o cadena de entrada en Σ∗ no
compila es decir que no pertenece a L, es decir que no sigue las reglas del lenguaje
de programación.
Comentario: Evidentemente, el compilador es un sistema que además de resolver el pro-
blema de decisión aporta como valor agregado un listado de errores en el caso de no poder
compilar y el código objeto en el caso de compilar. El problema P (compilación), es un
problema de pertenencia de un conjunto: ¾pertenece el programa w al conjunto in�nito
de programas L escritos en un lenguaje de programación particular?. Si L fuese �nito
resultaría sencillo de resolver, pero como afortunadamente (para quienes programan) L es
in�nito (se pueden escribir in�nitos programas utilizando un lenguaje de programación)
se debe buscar el modelo �nito de L que permita reconocer un programa bien escrito en
un lenguaje de programación dado. Este modelo �nito es justamente lo que la Teoría de
la Computación permite hacer.
Ejercicios propuestos
1. ¾Qué es un lenguaje formal?, Diferencia con los lenguajes naturales
2. Contestar verdadero (V) o falso (F):
a) Σ∗ es un lenguaje formado por el alfabeto.
b) La clausura de Kleene Σ∗ sobre el alfabeto Σ puede ser en algunos alfabetos un
conjunto �nito.
c) Dado el alfabeto Σ = {a,b} y ∆= {0,1}, la cadena w = a1b0 pertenece al alfabeto
Σ
∪
∆
d) Según la Jerarquía de Chomsky un lenguaje esta asociado un nivel de clasi�cación
de problemas asociado a una máquina
e) Un algoritmo es el conjunto de instrucciones que puede calcular
f ) No existe un lenguaje in�nito L en el alfabeto Σ = {a,b} para el cual L sea diferente
a L* (L ̸= L*)
3. Sea A, B y C lenguajes de un alfabeto Σ. En cada una de los ítems siguientes se indican la
expresión de 2 lenguajes. Señale si son siempre iguales y justi�que (indique contraejemplos
en caso de ser apropiado)
a) A (B
∪
C) y AB
∪
AC
b) A*B* y (AB)*
4. Enumere al menos 5 lenguajes (que no sean lenguajes de programación o idiomas) que
haya utilizado. Para cada uno de ellos identi�que el alfabeto y de ejemplo de una cadena
del lenguaje, describa el lenguaje.
14 CAPÍTULO 1. INTRODUCCIÓN
Capítulo 2
Lenguajes Regulares y autómatas
�nitos
Los lenguajes regulares, de tipo 3 según la jerarquía de Chomsky, son aquellos que son
reconocidos por autómatas de estados �nitos, son denotados por expresiones regulares y
generados por gramáticas regulares. Estos lenguajes contienen a todos los lenguajes �nitos
generados a partir de cualquier alfabeto. Los lenguajes in�nitos tipi�cados como regulares
poseen ciertas propiedades que lo caracterizan y distinguen de otros lenguajes más complejos
(ver tema sobre las propiedades y algoritmos de decisión de los lenguajes regulares).
2.1. Autómatas de estados �nitos
Los Autómatas de Estados Finitos (AF): Describen, reconocen y de�nen a los LenguajesRegulares. Es el modelo matemático de un sistema con estados y salidas discretas. Los Tipos
de Autómatas Finitos son:
1. Autómata Finito Determinista (AFD). No pueden estar en más de un estado simultá-
neamente.
2. Autómata Finito No Determinista (AFN). Puede estar en varios estados al mismo tiempo.
2.1.1. Autómatas �nitos determinista (AFD)
Un AFD es una quíntupla A = (Q , Σ, δ, q0, F), siendo:
Q = conjunto �nito de estados.
Σ = conjunto �nito de símbolos del alfabeto.
q0 = es el estado inicial (denotado con �echa → a inicio)
F = conjunto de estados �nales (o estados de aceptación), F ⊆ Q
δ = La función de transición entre estados, δ: Q x Σ → Q.
15
16 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
En los AFD debe cumplirse que: Para toda a que esta en Σ existe exactamente una transición
de salida de cada estado, es decir la función de transición dado un estado y un valor de entrada
se obtiene como resultado siempre un solo valor (estado).
Las siguientes son las tres formas para expresar y representar la función de transición, las
cuales son equivalentes entre si, cualquiera de ellas es su�ciente para completar el diseño del
AFD:
1. Diagrama de Transición: representado a través de un grafo. Un grafo G = (V,E)
consiste de un conjunto �nito de vértices (o nodos) V y un conjunto �nito de pares de
vértices (o aristas) E llamados enlaces (los cuales son bidireccionales).
Un camino en un grafo es una secuencia de vértices V1, V2, ... , Vk, con k ≥ 1, tal que hay
un enlace (Vi,Vi+1) con 1 ≤ i ≤ k. La longitud del camino es k-1. Si V1 = Vk entonces
el camino es un ciclo.
Una clase de grafo dirigido Dígrafo G =(V,E), consiste en un conjunto �nito de vértices
V (o nodos) y un conjunto �nito de pares ordenados de vértices E llamados arcos (una
sola dirección). Un arco de v a w se denota como v → w.
Un camino en un dígrafo es una secuencia de vértices V1, V2, ... , Vk, con k ≥ 1, tal que
Vi → Vi+1 es un arco con 1 ≤ i ≤ k. La longitud del camino es k-1. El camino es de V1
a Vk (importa la dirección). Si v → w es un arco entonces v es predecesor de w y w es
sucesor de v.
Ejemplo: Dado el Grafo G = ({1,2,3,4}, {i → j | i < j })
1,2,3,4 es un camino de longitud 3 de 1 a 4.
1,4 es un camino de longitud 1 de 1 a 4.
3,3 no es un camino.
3 es un camino de longitud 0 de 3 a 3?
Por notación, dado un AFD si p y q estan en Q y a en Σ, se de�ne la transición δ(q,a) =
p. como un arco (enlace) etiquetado a entre el estado (vértice) q y el estado (vértice) p.
Los estados o vértices de aceptación se denotan grá�camente con un doble círculo. Por
ejemplo si r esta en F debe ser denotado con doble círculo como se observa en la �gura
2.1.
Figura 2.1: Ejemplo de transición en AFD
2. Función de transición: representada a través de una función. Una función asigna a cada
elemento de un conjunto (Conjunto Dominio) un elemento de otro conjunto (Conjunto
Rango o Codominio). Así la función f se denota f : A → B, siendo A el dominio y B
el rango. Por ejemplo, la siguiente función f(x)= x2, se de�ne f: N → N, donde N es el
conjunto de los números naturales.
Los tipos de funciones son:
Inyectiva: Si a1 ̸= a2, entonces f(a1) ̸= f(a2)
2.1. AUTÓMATAS DE ESTADOS FINITOS 17
Cuadro 2.1: Estructura de la Tabla de Transición
δ Símbolos de Σ
Estados Estados
Sobreyectiva: Si todo elemento de B es imagen de alguno de A, es decir la función
inversa 1 f−1(b) ̸= ϕ, para todo b en conjunto Rango o Codominio.
La función de transición de un AFD esta de�nida como δ: Q x Σ → Q, es decir tiene
como dominio cualquier par del producto cartesiano (Q x Σ) del conjunto de estados Q y
el alfabeto de entrada Σ, y da como resultado un elemento del conjunto rango de estados
Q. En la �gura 2.1 se muestra un ejemplo de una función de transición δ(q,a) = p.
3. Tabla de Transiciones: representada a través de una matriz. La tabla tiene en las
columnas todas las entradas del alfabeto Σ y en las �las los estados de Q, por lo que
el par FilaxColumna representa el dominio de la función de transición (Q x Σ). Por
notación, en la tabla se escriben los estados de aceptación o estados �nales con asterisco
al lado del estado y el estado inicial con una �echa. En cada celda interna de la tabla se
muestra el resultado de la transición (codominio) es decir el estado Q al cual se realiza
la transición dado la �la y la columna de la posición de la celda respectiva. En los AFD
cada celda de la tabla debe tener un estado, no se permiten celdas vacias. Ver cuadro
2.1.
Ejemplo: Dado Σ = { 0, 1 } y el lenguaje L = { x | x en Σ∗ y x comienza con 0 }, es decir
todas las cadenas binarias que comienzan con 0. El AFD que lo reconoce, en sus tres represen-
taciones, es el siguiente:
M = (Q, Σ, δ, q0, F)
Donde Q = {q0, q1, q2}, Σ= {0,1} y F = {q1}
1. Diagrama de transición: se observa en la �gura 2.2.
Figura 2.2: Ejemplo de AFD: cadenas binarias que comienzan con cero
1Dada f:A → B, la función inversa f−1:B → A, se de�ne como f−1(b) = {x | x en A y f(x) = b } para todo
b en B
18 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.2: Ejemplo de Tabla de Transición
δ 0 1
→ q0 q1 q2
*q1 q1 q1
q2 q2 q2
2. Función de transición δ
δ(q0, 0) = q1
δ(q0, 1) = q2
δ(q1, 0) = q1
δ(q1, 1) = q1
δ(q2, 0) = q2
δ(q2, 1) = q2
3. Tabla de transición: se observa en el cuadro 2.2
Las tres representaciones del AFD son equivalentes y cada una de ellas es su�ciente para
expresar el modelo. Sin embargo, debe enterderse la relación entre ellas aunque se seleccione
solo una de ellas para representar al autómata.
Ejecución de un Autómatas de estados �nitos determinista (AFD)
Para la ejecución formal de un AFD se utiliza la de�nición de la función de transición
extendida sobre cadenas δ̂. La de�nición de su dominio y rango es: δ̂ = Q x Σ∗ → Q. La
de�nición recursiva de la función δ̂ se de�ne:
1. Caso base para la cadena vacía λ: Para todo q en Q, δ̂(q,λ) = q. Esto quiere decir que
desde cualquier estado la cadena vacía λ no cambia el estado del AFD.
2. Caso recursivo para cadenas de cardinalidad mayor que 1: Para todo w en Σ∗ y a en Σ,
se cumple que δ̂(q,wa) = δ(δ̂(q,w),a).
Por ejemplo: Dado el AFD anterior que reconoce el lenguaje sobre Σ = {0, 1} y L = {x | x en
Σ∗ y x comienza con 0}, pruebe si las cadenas w1 = 010 y w2 = 101 están en el lenguaje L:
1. δ̂(q0,010)
= δ(δ̂(q0,01),0)
= δ(δ(δ̂(q0,0),1),0)
= δ(δ(δ(δ̂(q0, λ),0),1),0)
→ δ(δ(δ(q0, 0), 1), 0) → (δ(q1, 1), 0) → δ(q1, 0) = q1 → Se acepta al terminar de procesar
la cadena 010 y quedar en un estado de aceptación δ̂(q0,010) = q1 (q1 está en F)
2.1. AUTÓMATAS DE ESTADOS FINITOS 19
2. δ̂(q0,101)
= δ(δ̂(q0,10),1)
= δ(δ(δ̂(q0,1),0),1)
= δ(δ(δ(δ̂(q0, λ),1),0),1)
→ δ(δ(δ(q0, 1), 0), 1) → (δ(q2, 1), 0) → δ(q2, 0) = q2 → No se acepta al terminar de pro-
cesar la cadena 101 y quedar en un estado que no es de aceptación δ̂(q0,101) = q2 (q2 no
está en F)
Lenguaje aceptado por un AFD
Dado M = (Q, Σ, δ, q0, F) un AFD, el lenguaje L aceptado por M está de�nido por:
L(M)= { w | w en Σ∗ y δ̂(q0,w) pertenece a F }
Es decir, el lenguaje de M, es un conjunto de cadenas w que llevan al autómata M desde q0 a
un estado de aceptación. Si L es un L(M) para algún AFD M, entonces decimos que L es un
Lenguaje Regular. Nota importante: Para poder veri�car si la cadena w está (es aceptada) o
no está (no es aceptada) en L se debe terminar de procesarse la cadena w (desde el principio
hasta el �nal).
2.1.2. Autómatas �nitos no determinista (AFND)
Son autómatas de estados �nitos que tienen la capacidad de estar en más de un estado
simultáneamente. No hay que considerar todos los casos en cada estado, ya que permiten cero,
una o más transiciones de salida de un estado para el mismo símbolo del alfabeto de entrada.
Ellos tienen la ventaja de ser más compactos, �exibles y fáciles de diseñar que los AFD.
Esta compuesta por la misma tupla de elementos que un AFD A = (Q, Σ, δ, q0, F), la diferencia
es la de�nición de la función δ̂ y el rango de la función de transición, δ: Q x Σ → 2Q ó también
δ: Q x Σ → Q∗
En la �gura 2.3 se muestra eldiagrama de transición δ(q,a) = {p,r}, donde el AFND dado
el estado q y el símbolo a se mueve a dos estados (un conjunto de estados) simultáneamente.
Como δ: Q x Σ → Q∗, entonces δ(q,a) = R, donde R ⊆ Q.
Figura 2.3: Ejemplo de transición en AFND
Ejecución de un Autómatas de estados �nitos determinista AFND
Para la ejecución formal de un AFND se utiliza la de�nición de la función de transición
extendida sobre cadenas δ̂ : Q x Σ∗ → Q∗, de�nida recursivamente así:
20 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.3: Tabla de transición: Lenguaje de las cadenas binarias que terminan en 01
δ 0 1
→ q0 {q0, q1} {q0}
q1 ϕ {q2}
*q2 ϕ ϕ
1. Caso base para la cadena vacía λ: δ̂(q,λ) = {q}. Es desde cualquier estado del autómata
la cadanea vacía λ no cambia de estado.
2. Paso recursivo para cadenas de cardinalidad mayor que 1: δ̂(q,xa) = { r | para algún p
en δ̂(q,x), δ(p,a) = r }. Sea w de la forma w = xa donde a es el símbolo �nal (su�jo de
longitud 1) de w y x el resto de w.
δ̂(q,x) = {p1, p2, ..., pn} sea
∪k
i=1 δ(pi,a) = {r1, r2, ..., rn}
Entonces δ̂(q,x) = δ(δ̂(q,x),a) = {r1, r2, ..., rn}, ver �gura 2.4.
La extensión para δ̂ de Q∗xΣ:
δ̂((P,w) =
∪
qenP δ̂(q,w), para todo conjunto de estados P en Q
∗
Figura 2.4: De�nición de δ̂ en un AFND
Ejemplo: Dado el alfabeto Σ = {0,1} y el lenguaje de todas las cadenas binarias que terminan
en 01, L= { x | x en Σ∗ y x termina en 01 }, hallar el AFND que lo reconozca
L = { 01, 0001, 101, 1001, 10101, ... } A = (Q, Σ, δ, q0, F), donde:
Q = {q0, q1, q2}, Σ = {0,1} y F = {q2}
En la �gura 2.5 y el cuadro 2.3 se observa el AF que reconoce el lenguaje. Para las cadenas
Figura 2.5: Ejemplo de AFND: cadenas binarias que terminan en 01
2.1. AUTÓMATAS DE ESTADOS FINITOS 21
w1 = 01 y w2 = 10101 se muestra la ejecución formal a partir de la función de transición
extendida δ̂:
1. δ̂(q0,01)
= δ(δ̂(q0,0),1)
= δ(δ(δ̂(q0, λ),0),1)
→ δ(δ({q0},0),1)
→ δ({q0, q1},1) = δ(q0,1)
∪
δ(q1,1) = {q0}
∪
{q2} = {q0, q2},→ Acepto porque {q0, q2}
∩
{q2} ̸= ϕ, es decir al menos uno de los estados del autómata es de aceptación (pertenece
a F) luego de procesar la cadena.
2. δ̂(q0,10101) = δ(δ̂(q0,1010),1) = δ(δ(δ(δ(δ(δ̂(q0, λ),1),0),1),0),1)
→ δ(δ(δ(δ(δ({q0},1),0),1),0),1), δ({q0},1) = {q0}
→ δ(δ(δ(δ({q0},0),1),0),1), δ({q0},0) = {q0, q1}
→ δ(δ(δ({q0, q1},1),0),1), δ({q0, q1},1) = δ(q0,1)
∪
δ(q1,1) = {q0}
∪
{q2} = {q0, q2}
→ δ(δ({q0, q2},0),1), δ({q0, q2},0) = δ(q0,0)
∪
δ(q2,0) = {q0, q1}
∪
ϕ = {q0, q1}
→ δ({q0, q1},1), δ({q0, q1},1) = δ(q0,1)
∪
δ(q1,1) = {q0}
∪
{q2} = {q0, q2}
Acepto porque {q0, q2}
∩
{q2} ̸= ϕ, es decir al menos uno de los estados es de aceptación
(pertenece a F).
Lenguaje aceptado por un AFND
Dado M = (Q, Σ, δ, q0, F) un AFND, el lenguaje L aceptado por M está de�nido por:
L(M) = { w | w en Σ∗ y δ̂(q0,w)
∩
F ̸= ϕ }
Es el conjunto de cadenas pertenecientes a Σ∗ tal que ejecutar el AFND desde el estado inicial
q0 con la cadena w, la función de transición extendida δ̂(q0,w) contiene al menos un estado de
aceptación (es diferente del vacío la intersección con F).
Equivalencia entre AFD y AFND
Todo Lenguaje regular puede describirse con ambos tipos de autómatas AFND y AFD.
Generalmente un AFND es más fácil de diseñar (capturar su modelo) y un AFD es mas fácil
de implementar (ejecutar para el conocimiento de cadenas). El AFD más grande puede tener
2n estados y el AFND más pequeño solo tiene n estados.
Teorema 1. Si L es aceptado por un AFND entonces existe un AFD que acepta L (es decir,
ambos aceptan la misma clase de lenguaje: lenguajes regulares).
Algoritmo para la Construcción de Subconjuntos:
Este algoritmo permite a partir de un AFND obtener un AFD equivalente que reconoce el
mismo lenguaje. Su nombre se debe a que se intenta construir todos los subconjuntos del
conjunto de estados del AFND.
AFN N = (QN , Σ, δN , q0 , FN )
AFD D = (QD, Σ, δD, {q0} , FD)
Tal que L(N) = L(D) (el lenguaje reconocido por el autómata N sea el mismo que el lenguaje
22 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.4: Tabla de transición δN : Lenguaje de las cadenas binarias que terminan en 01
δN 0 1
→ q0 {q0, q1} {q0}
q1 ϕ {q2}
*q2 ϕ ϕ
reconocido por el autómata D, por tanto sean equivalentes)
Algoritmo:
1. Σ son iguales para N y D.
2. QD es el conjunto de los subconjuntos de QN , (Conjunto potencia QD = Q
∗
N ). No todos
los estados de QD son accesibles desde q0, los estados inalcanzables desde el estado inicial
serán eliminados.
3. FD es el conjunto S de subconjuntos de QN (S ⊆ QN ) tal que S
∩
FN ̸= ϕ. Es decir
FD contiene todos los conjuntos de estados de N que incluyen al menos un estado de
aceptación de N.
4. Para todo S ⊆ QN y a en Σ, entonces δD(S,a) =
∪
pϵS δN (p,a).
Ejemplo: Dado el AFDN de la �gura 2.5 y el cuadro 2.4 denotado como N = (QN , Σ, δN , q0,
FN ), con Σ= {0,1} y QN = {q0, q1, q2}, FN = {q2}. Obtener D un AFD tal que L(N) = L(D)
a través del algoritmo de construcción de subconjuntos.
Figura 2.6: Relación AFDN y AFD: construcción de subconjunto sobre el AFND de la �gura
2.5
1. Σ = {0, 1}
2. D = (QD, Σ, δD, {q0}, FD)
3. QD = {ϕ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}} (Conjunto de todos los
subconjuntos de Q)
2.1. AUTÓMATAS DE ESTADOS FINITOS 23
Cuadro 2.5: Tabla de transición δD a través de la construcción de subconjuntos
δD 0 1
q0 → {q0} {q0, q1} {q0}
q1 {q0, q1} {q0, q1} {q0, q2}
q2 *{q0, q2} {q0, q1} {q0}
4. FD = {{q2}, {q0, q2}, {q1, q2}, {q0, q1, q2}}
5. Generar δD, ver cuadro 2.5 y �gura 2.6 (se renombran los estados {q0} = q0, {q0, q1}
= q1, {q0, q2} = q2)
a) δD({q0},0) = δN (q0,0) = {q0, q1}
b) δD({q0},1) = δN (q0,1) = {q0}
c) δD({q0,q1},0) = δN (q0,0)
∪
δN (q1,0) = {q0,q1}
∪
ϕ = {q0,q1}
d) δD({q0,q1},1) = δN (q0,1)
∪
δN (q1,1) = {q0}
∪
{q2} = {q0,q2}
e) δD({q0,q2},0) = δN (q0,0)
∪
δN (q2,0) = {q0,q1}
∪
ϕ = {q0,q1}
f ) δD({q0,q2},1) = δN (q0,1)
∪
δN (q2,1) = {q0}
∪
ϕ = {q0}
A continuación se realiza la ejecución de AFD resultante para evaluar la cadena w=10101:
δ̂D({q0},10101) =
δD(δ̂D({q0},1010),1) =
δD(δD(δD(δD(δD(δ̂D({q0}, λ),1),0),1),0),1)
δD(δD(δD(δD(δD({q0},1),0),1),0),1)
= δD(δD(δD(δD(δD({q0},1),0),1),0),1)
= δD(δD(δD(δD({q0},0),1),0),1)
= δD(δD(δD({q0, q1},1),0),1)
= δD(δD({q0, q2},0),1) = δD({q0, q1},1) = {q0, q2}
Se acepta la cadena porque {q0, q2} esta en FD
La demostración de este algoritmo se encuentra en el libro de Hopcroft [2] : Se demuestra
por inducción sobre el tamaño de w, donde el caso base δ̂N (q0, λ) = δ̂N ({q0}, λ) y para el caso
inductivo δ̂N (q0,w) = δ̂N ({q0},w).
2.1.3. Autómatas �nitos no determinista con transiciones nulas (AFND-λ)
Es un AFND que permite transiciones para la cadena vacía λ. Antes los AF no se movían
con la cadena vacía, es decir δ̂N (q, λ) = {q} y δ̂D(q, λ) = q, los AF se quedaban en el
mismo estado cuando procesan a la cadena vacía. Ahora con AFND-λ se tienen transiciones
espontáneas, es decir sin recibir o procesar ningún símbolo de la entrada. Se aplica si λ no
pertenece al conjunto de símbolos de Σ. Su utilidad:
24 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Facilidad para modelar (autómatas más sencillos y con menos estados y transiciones).
Relación directa con las expresiones regulares (equivalencia demostrada formalmente)
Un AFND-λ es una quíntupla: A=(Q, Σ, δ, q0, F), siendo:
Q = conjunto �nito de estados.
Σ = conjunto �nito de símbolos del alfabeto.
q0 = es el estado inicial (denotado con �echa →) a inicio
F = conjunto de estados �nales (o estados de aceptación). F ⊆ Q
δ = la función de transición entre estados δ: Q x Σ
∪
{λ} → Q∗.
Ejemplo: Dado L = {0n1m2p | n,m,p ≥ 0 }, el lenguaje de todas las cadenas de 0, 1 o más
digitos cero (0n) seguidas de 0, 1 o más dígitos uno (1m), y seguidas de 0, 1 o más digitos dos
(2p). Los siguientes autómatas de las �guras 2.7 y 2.8 reconocen a L:
En la tabla de transición 2.6, del AFND-λ puede o no asumirse la transición espontánea de
Figura 2.7: AFND para el lenguaje 0n1m2p
Figura 2.8: AFND-λ para el lenguaje 0n1m2pla cadena vacía λ. Es decir, δ̂(q,λ) = {q}. Por ejemplo en el estado q2, puede ser λ pero sin
embargo también es ϕ
∪
{q2}.
2.1. AUTÓMATAS DE ESTADOS FINITOS 25
Cuadro 2.6: Tabla de transición de un AFND-λ
δ 0 1 2 λ
→ q0 {q0} ϕ ϕ {q1}
q1 ϕ {q1} ϕ {q2}
* q2 ϕ ϕ {q2} ϕ
Ejecución de un Autómatas de estados �nitos no determinista AFND-λ
Dada una cadena w y un AFND-λ, para reconocer dicha cadena se debe aplicar la función
extendida para cadenas δ̂: Q x Σ∗ → Q∗. Donde δ̂(q,w) es el conjunto de todos los estados
pi tal que se puede ir de q a cada pi por un camino etiquetado w que puede incluir arcos
etiquetados λ. Para calcular este camino es necesario de�nir el término de la λ-clausura(q) de
un estado q (q en Q) como, el conjunto de todos los estados a los cuales se puede llegar a partir
de q siguiendo un camino de arcos únicamente etiquetados con λ.
La de�nición recursiva de λ-clausura(q):
Base: λ-clausura(q) = {q} , es decir por de�nición δ̂(q,λ) = {q}, podemos imaginarnos
un bucle de un estado a si mismo etiquetado λ. Ver �gura 2.9.
Paso inductivo: Si δ̂ es la función de transición de AFND-λ y p está en la λ-clausura(q),
es decir δ̂(q, λ) = {p} entonces la λ-clausura(q) también contiene los estados δ̂(p,λ). Ver
�gura 2.9.
Figura 2.9: Ejemplo de la de�nición de λ-clausura en un AFND-λ
La de�nición de la función de transición extendida δ̂ de los AFND-λ, con la que se pueden
ejecutar este tipo de autómata, es la siguiente:
1. δ̂(q0, λ) = λ-clausura(q0)
2. Para todo w en Σ∗ y a en Σ, δ̂(q,wa) = λ-clausura(P) con P ⊆ Q, Donde:
λ-clausura(P) = { p | para algún r en δ̂(q,w), p en δ(r,a) } , Aplicar λ-clausura a
cada p en P.
3. Como aplicar la función δ a un conjunto de estados R. δ(R,a) =
∪
qenR δ(q,a), R ⊆ Q
26 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Figura 2.10: Ejemplo de la de�nición de λ-clausura en un AFND-λ en caso inductivo
4. Como aplicar la función δ̂ a un conjunto de estados R. δ̂(R,a) =
∪
qenR δ̂(q,a), R ⊆ Q.
Entonces se tienen las siguientes de�niciones δ̂(q,w) = δ̂(q,x) = {r1, r2, ..., rk} con w =
xa.∪k
i=1 δ(ri,a) = {p1, p2, ..., pm} y δ̂(q,w) =
∪m
j=1 λ-clausura(pj). Ver �gura 2.10.
Ejemplo: Dada la cadena w = 02 determinar si pertenece o no al lenguaje 0n1m2p reconocido
por el AFND-λ de la �gura 2.8
De�nición de la λ-clausura de los estados del autómata:
λ-clausura(q0) = {q0, q1, q2}
λ-clausura(q1) = {q1, q2}
λ-clausura(q2) = {q2}
Aplicando la función de transición extendida δ̂:
δ̂(q0,02) = λ-clausura(δ(δ̂(q0,0),2)) = λ-clausura(δ(λ-clausura(δ(δ̂(q0,λ),0)),2))
λ-clausura(δ(λ-clausura(δ({q0, q1, q2},0)),2)) → δ̂(q0, λ) = λ-clausura(q0) = {q0, q1, q2}
λ-clausura(δ(λ-clausura({q0}),2)) → δ({q0, q1, q2},0) = {q0}
∪
ϕ
∪
ϕ = {q0}
= λ-clausura(δ({q0, q1, q2},2)) → λ-clausura({q0}) = λ-clausura(q0) = {q0, q1, q2}
λ-clausura(q2) → δ({q0, q1, q2},2) = ϕ
∪
ϕ
∪
{q2} = {q2}
{q2} Acepto la cadena w = 02 ya que δ̂(q0,02)
∩
F = {q2} ̸= ϕ.
Lenguaje aceptado por un AFND-λ
Dado un AFND-λ E = (Q, Σ, δ, q0, F) el L(E) se de�ne como:
L(E)= { w | w en Σ∗, δ̂(q0,w)
∩
F ̸= ϕ }
2.1. AUTÓMATAS DE ESTADOS FINITOS 27
El lenguaje L(E), el reconocido por el autómata E, es el conjunto de cadenas de Σ∗ que al
aplicar la función de transición extendida δ̂ se obtiene un conjunto de estados de Q donde al
menos uno pertenece al conjunto de estados de aceptación (F).
Equivalencia entre AFD y AFND-λ (construcción de subconjuntos de λ)
Teorema 2. Si L es aceptado por un AFND con λ-transiciones entonces L es aceptado por
un AFND sin λ-transiciones.
Teorema 3. Un lenguaje regular L es aceptado por un AFND con λ-transiciones si y sólo si
es aceptado por un AFD.
A partir de estos teoremas se deriva un algoritmo para pasar de un AFND-λ a un AFD,
es decir para eliminar las transiciones λ y obtener un autómata equivalente que reconozca el
mismo lenguaje de forma deterministica.
Dado E un AFND-λ se quiere lograr que L(E) = L(A), con y A un AFD, es decir δ̂E(q0E ,w)
= δ̂D(q0D,w) para todo w en L:
E (AFND-λ) = (QE ,Σ, δE , q0E , FE)
D (AFD) = (QD,Σ, δD, q0D, FD)
Algoritmo:
1. q0D = λ-clausura(q0E)
2. QD = Q
∗
E , es decir el conjunto de subconjuntos de QE
3. FD = { s | s en QD y {s}
∩
FE ̸= ϕ }
4. δD(S,a) para todo a en Σ y S en QD, se cumple:
δD(S,a) =
∪n
j=1 λ-clausura(rj),
{r1, r2, ..., rn} =
∪k
i=1 δE(pi,a) con S = {p1, p2, ..., pk}. Ver �gura 2.11
Figura 2.11: Construcción de subconjuntos λ en un AFND-λ
28 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.7: Tabla de transición δD a través de la construcción de sunconjuntos de λ
δD 0 1 2
q0 → {q0, q1, q2} {q0, q1, q2} {q1, q2} {q2}
q1 {q1, q2} ϕ {q1, q2} {q2}
q2 *{q2} ϕ ϕ {q2}
Ejemplo: Dado el AFND-λ E de la �gura 2.8, encontrar un AFD equivalente que reconozca
el mismo lenguaje.
E = (Q, Σ, δ, q0, F), donde Q = {q0, q1, q2}, Σ = {0, 1, 2} y F = {q2}. Se obtiene el AFD D
= (QD, Σ, δD, q0D, FD), aplicando el algorimos de construcción de subconjuntos de λ:
1. Σ = {0, 1, 2}
2. q0D = λ-clausura(q0) = {q0, q1, q2}
3. QD = {ϕ, {q0}, {q1}, {q2}, {q0, q1}, {q1, q2}, {q0, q2}, {q0, q1, q2}}
4. FD = {{q2}, {q1, q2}, {q0, q2}, q0, q1, q2}
5. Cálculo de δD: (ver cuadro 2.7)
Para el estado inicial {q0, q1, q2} se aplica la de�nición para todos los elementos de Σ:
* δD({q0, q1, q2},0) = λ-clausura(δE(q0, 0)
∪
δE(q1, 0)
∪
δE(q2, 0)) = λ-clausura({q0}
∪
ϕ
∪
ϕ)
= λ-clausura({q0}) = λ-clausura(q0) = {q0, q1, q2}
* δD({q0, q1, q2},1) = λ-clausura(δE(q0, 1)
∪
δE(q1, 1)
∪
δE(q2, 1)) = λ-clausura(ϕ
∪
{q1}
∪
ϕ)
= λ-clausura({q1}) = λ-clausura(q1) = {q1, q2}
* δD({q0, q1, q2},2) = λ-clausura(δE(q0, 2)
∪
δE(q1, 2)
∪
δE(q2, 2)) = λ-clausura(ϕ
∪
ϕ
∪
{q2})
= λ-clausura({q2}) = λ-clausura(q2) = {q2}
Para el estado {q1, q2} se aplica la de�nición para todos los elementos de Σ:
* δD({q1, q2},0) = λ-clausura(δE(q1, 0)
∪
δE(q2, 0)) = λ-clausura(ϕ
∪
ϕ) = λ-clausura(ϕ)
= ϕ
* δD({q1, q2},1) = λ-clausura(δE(q1, 1)
∪
δE(q2, 1)) = λ-clausura({q1}
∪
ϕ) = λ-
clausura({q1}) = λ-clausura(q1) = {q1, q2}
* δD({q1, q2},2) = λ-clausura(δE(q1, 2)
∪
δE(q2, 2)) = λ-clausura(ϕ
∪
{q2}) = λ-
clausura({q2}) = λ-clausura(q2) = {q2}
Para el estado {q2} se aplica la de�nición para todos los elementos de Σ:
* δD({q2},0) = λ-clausura(δE(q2, 0)) = λ-clausura(ϕ) = ϕ
* δD({q2},1) = λ-clausura(δE(q2, 1)) = λ-clausura(ϕ) = ϕ
* δD({q2},2) = λ-clausura(δE(q2, 2)) = λ-clausura({q2}) = λ-clausura(q2) = {q2}
Hay dos formas de interpretar la construcción de subconjuntos-λ, una para crear un AFD y
otra AFND. La idea es llegar a un AF más fácil de implementar (es decir obtener un AFD).
AFD: Se toma cada estado como un conjunto de etiquetas. Ver �gura 2.12
AFND: Se interpreta el contenido de la etiqueta de cada estado. Ver �gura 2.13
2.1. AUTÓMATAS DE ESTADOS FINITOS 29
Figura 2.12: AFD equivalente del AFND-λ de la �gura 2.8 a través de la Construcción de
subconjuntos λ
Figura 2.13: AFND equivalente del AFND-λ de la �gura 2.8 a través de la Construcción de
subconjuntos λ
2.1.4. Herramientas, implementación y uso de Lenguajes regulares
Implementación de un AFD: programación basada en autómatas
La simulación de un AFD resulta un enfoque de programación que permite aumentar el
nivel de abstracción ante la solución de un problema. El siguiente algoritmo (no recursivo)
expresado en pseudocódigo muestra el funcionamiento del AFD de la �gura 2.2:
INICIO
Conjunto Q[Estado] = {q0, q1, q2}
Conjunto Σ[Simbolo]= {0,1}
Conjunto F[Estado] = {q1}
Estado Actual = q0
Simbolo A
A = LeerSimboloCadena()
Mientras a ̸= λ entonces
Actual = transicionδ(Actual, A)
A = LeerSimboloCadena()
fin Mientras
Si Pertenece(Actual,F) entonces
30 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Imprimir("Se acepta la cadena")
sino
Imprimir("No se acepta la cadena")
fin Si
FIN
Función transicionδ(Estado q, Símbolo a): Estado
Estado S
Selección
q = q0 y a = 0: S = q1
q = q0 y a = 1: S = q2
q = q1 y a = 0: S = q1
q = q1 y a = 1: S = q1
q = q2 y a = 0: S = q2
q = q2 y a = 1: S = q2
fin Selección
Retornar S
fin Función
Dondese asume que se tiene los siguientes tipos de datos: Conjunto (paramétrico por el
tipo de elemento), Estado, Simbolo. Para ellos se tiene las siguientes operaciones:
LeerSimboloCadena() que permite obtener desde la entrada estándar un Símbolo de la
cadena de entrada w (desde el comienzo, secuencialmente uno a uno)
Imprimir(CadenaCaracter) función que permite imprimir la salida del autómata, si
acepta o no la cadena de entrada
Pertenece(Estado A, Conjunto B[Estado]), es una operación del tipo de dato Con-
junto que determina si el elemento A (del tipo Estado) pertenece al Conjunto de Estados
B.
Una posible implementación del algoritmo anterior en lenguaje C se muestra a continuación:
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
enum estados { q0, q1, q2 };
void transicion(enum estados *estado, char a) // función de transición
{
switch(*estado) {
case q0:
if(a == '0') {
2.1. AUTÓMATAS DE ESTADOS FINITOS 31
putchar(a);
*estado = q1;
}
else {
if(a == '1') {
putchar(a);
*estado = q2;
}
}
break;
case q1:
if(a == '0' || a == '1') {
putchar(a);
*estado = q1;
}
break;
case q2:
if(a == '0' || a == '1') {
putchar(a);
*estado = q2;
}
break;
}
}
int main()
{
char c;
string cad;
enum estados state = q0;
cout << "AFD que reconoce todas las cadena binarias que comienzan con 0" << endl;
cout << "Estado inicial: " << state << endl;
c = getchar();
cad = c;
while((c == '0') || (c == '1')) {
transicion(&state, c);
cout << " Estado actual: " << state << endl;
c = getchar();
if ((c == '0') || (c == '1')) cad = cad + c;
}
if (state == q1) cout << "La cadena " << cad << " SI esta en el lenguaje" << endl;
else cout << "La cadena " << cad << " NO esta en el lenguaje" << endl;
return 0;
}
32 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
2.1.5. Preguntas y respuestas, ejercicios resueltos y propuestos
Preguntas y respuestas
1. ¾Qué es un autómata?. Es una máquina abstracta, dispositivo teórico o modelo matemá-
tico que procesa una secuencia �nita de símbolos de un alfabeto, cambiando su estado de
acuerdo al símbolo que está leyendo o procesando, lo que permite saber si una cadena se
encuentra dentro o no de un lenguaje dado. Tiene un conjunto �nitos de estados posibles
y muestra las posibles transiciones entre los estados.
2. ¾Por qué en los AF se tiene siempre un sólo estado de inicial y uno o más estados �nales?.
El objetivo de una AF es aceptar cadenas de un lenguaje y para eso necesita estados
de aceptacón, por tanto el conjunto F no puede ser vacío, pero si puede tener uno o
más caminos para reconocer esas cadenas (tener mas de un estado en F). Con respecto
al estado inicial se necesita sólo uno, pues el AF necesita saber de forma precisa por
donde comenzar el funcionamiento de la máquina. Si se tiene más de un estado inicial el
AF debe seleccionar por donde comenzar, lo cual resultaría complicado para un modelo
matemático sencillo. De forma análoga ocurre en los lenguajes de programación donde
sólo hay un inicio para el programa (main) pero puede tener mas de un �nal (exit).
3. ¾Por qué un AF debe terminar de procesar la cadena de entrada para saber si está o no
en el lenguaje?. La mayoría de los autómatas o máquinas de reconocimiento (excepto la
Máquina de Turing) tienen esta restricción que les permite simpli�car el funcionamiento
de su modelo. Si bien es cierto que para algunos lenguajes no hace falta recorrer toda la
cadena pues su de�nición no lo requiere (por ejemplo puede estar relacionada sólo con el
pre�jo de las cadenas), hacer que estos casos funcionen como los demás es lo más simple
y general en un modelo matemático.
4. ¾Por qué el conjunto de estados de un AF es �nito? Una de las características de los
autómatas �nitos es que el conjunto de estados es �nito. Esto se debe a una propiedad
matemática sobre los lenguajes regulares (relación de equivalencia) que establece parti-
ciones �nitas sobre el lenguaje (aunque el lenguaje puede ser in�nito). Esta propiedad es
diferente en otros tipos de lenguajes más complejos pues las particiones se hacen in�nitas
y por ende el número de estados para representarlas.
5. ¾Puede obtener un AFND algorítmicamente a partir de un AFD?, ¾por qué? El pro-
cedimiento de la construcción de subconjuntos permite llevar de un AFND a AFD, es
decir eliminar el no determinismo. El no determinismo implica el manejo de opciones o
alternativas en cada paso de transición generando instancias simultáneas del Autómata
en cada alternativa. El caso contrario parte de un AFD y se quiere obtener un AFND,
es decir agregar no determinismo al autómata. Este proceso no tiene un algortimo, pero
si dicho algoritmo pudiera existir tendría que ser en si no determinístico, es decir aplicar
alternativas �nitas en cada paso de transición que incluso podría no tener sentido, sería
muy complejo e incluso di�cil de aplicar en algunos lenguajes regulares.
6. ¾Qué signi�ca la equivalencia de autómatas?. Dos autómatas son equivalente cuando
reconocen exactamente el mismo lenguaje. Es necesario distinguir entre ser iguales y ser
equivalente. Dos autómatas diferentes pueden tener diferente cantidad de estados, con
diferentes transiciones e incluso diferente cantidad de estados de aceptaciión, es decir
2.1. AUTÓMATAS DE ESTADOS FINITOS 33
son diferentes en todo sentido y por tanto no son iguales. Sin embargo, estos autómatas
diferentes, M1 ̸= M2, son capaces de procesar cadenas de Σ
∗ y reconocer el mismo
lenguaje L (todas y cada una de las cadenas que forman a L, ni una más ni una menos),
en ese caso son llamados autómatas equivalentes, es decir L(M1) = L(M2).
Ejercicios resueltos
1. Determine las diferencias entre un AFD y un AFND. Ver el cuadro 2.8
2. Aplicaciones de la vida real que pueden ser vistos como AF. Algunas aplicaciones intere-
santes de los AF están referidas al almacenamiento de diccionarios como los usados en
los celulares, en la que se utilizan sus características para hacer búsquedas, inserciones o
modi�caciones rápidas. Así como también para mejorar el ordenamiento y búsqueda en
otros tipos de aplicaciones como los circuitos digitales, texto, secuencias lógicas de fun-
cionamiento (como la maquinaria industrial, robótica) y otras. También son útiles para
el modelado de aquellos casos en los que a partir de una acción anterior se puede llegar a
un conjunto determinado de destinos, pero no se tiene certeza anticipada de cuál de ellos
es el indicado, utilizados para modelar protocolos de comunicación, sistemas distribuidos,
plani�cación, etc.
3. Modelar un AF que reconozca un identi�cador válido en el lenguaje de programación C.
Un identi�cador es un nombre que de�ne a una variable, una función o un tipo de datos.
Un identi�cador válido ha de empezar por una letra o por el carácer de subrayado _,
seguido de cualquier cantidad de letras, dígitos o subrayados. Además: No debe contener
caracteres especiales, tales como @, $, #, no debe haber espacios en blanco en los iden-
ti�cadores.
El AF que reconoce este lenguaje es el siguiente:
A = (Q, Σ, δ, q0, F), donde Q = {q0, q1}, Σ son todos los caracteres alfanuméricos y ca-
racteres especiales permitidos (tales como -,_,.) , F = {q1}, y δ se expresa en el diagrama
de transición de la �gura 2.14 , donde se observa dos conjuntos de caracteres:
A = conjunto de caracteres alfabéticos
B = conjunto de caracteres alfabéticos, numéricos y subrayados
Figura 2.14: AF que reconoce un identi�cador en el lenguaje C
Existen palabras propias del lenguaje (palabras reservadas) que no pueden ser usadas
como identi�cadores ej: if, do, while, etc. Cómo puede modi�car el AF anterior para no
considerar como identi�cadores a las palabras reservadas del lenguaje.
34 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.8: Tabla comparativa de AFD y AFND
Característica AFD AFND
Función de
transición δ
δ: Q x Σ → Q, rango es un elemento
de Q
δ: Q x Σ → Q∗, rango es un subcon-
junto de Q
De�nición del
Lenguaje que
reconoce
L(M)={w|w ϵ Σ∗ yδ̂(q0,w) ϵ F },
Lenguaje regular L reconocido por
el AFD M
L(M)={w|w ϵ Σ∗ y δ̂(q0,w)
∩
F ̸=
ϕ}, Lenguaje regular L reconocido
por el AFND M
Estado actual Un solo estado actual en cada paso
del autómata
El estado actual puede ser un con-
junto de estados (subconjunto de
Q), es deir múltiples estados simul-
taneamente
Condición del
diagrama de
transición
Desde cada estado existe una tran-
sición de salida por cada símbolo de
Σ
No hay restricciones con respecto a
las transiciones, un símbolo de Σ
puede tener 0, 1 o más transciones
de salida desde el mismo estado
Condición de
la tabla de
transición
Cada posición de la celda de la ta-
bla debe tener sólo un estado (estar
completa)
Las posiciones de las celdas pueden
tener cualquier subconjunto de Q
(incluyendo el ϕ).
Utilidad Los AFD son los que se implemen-
tan para el reconocimiento de len-
guajes regulares, se usan para simu-
lar AFND
Los AFND se utilizan en lengua-
jes regulares con alfabetos grandes y
muchos estados, pues es más senci-
llo de modelar, tiene relación directa
con las expresiones regulares y son
utiles para aplicar operaciones sobre
autómatas
Facilidad de
modelado y
programación
El modelo de un AFD deben consi-
derar todo Σ en cada estado, esto lo
hace exhaustivo y difícil de diseñar.
En cambio su programación o imple-
mentación es un algortimo determi-
nístico (tiene de�nido que hacer en
cada caso) e�ciente
El modelo de un AFND es sencillo
pues no exige evaluar todo Σ en ca-
da estado, al contrario puede con-
siderar solo las opciones que acep-
tan las cadenas y muestra un dise-
ño más sencillo. Por el contrario, su
implementación requiere simular las
alternativas simultáneas en cada pa-
so de transición (búsqueda en un ár-
bol realizando backtracking) y pue-
de hacer complejo y poco e�ciente
su programación e implementación
2.1. AUTÓMATAS DE ESTADOS FINITOS 35
4. Modelar un AF que reconozca el conjunto de enteros y números en punto �otante o
también llamadas "literales numéricas".
En el lenguaje C, las siguientes expresiones son literales numéricas válidas: 3, +0, -2E+7,
13., -01, -14.4, 41.16, -.4E-7, 0.2E-20, 00E0, 01E-06. La letra E se re�ere a un exponente
y su presencia hace que el número subsiguiente sea un entero. Se supone que no existe
límite en el número de dígitos consecutivos en ninguna parte de la expresión (no hay el
problema de la precisión).
El AF que reconoce este lenguajs puede ser el siguiente: B = (Q, Σ, δ, q0, F), donde Q =
{qi | 0 ≤ i ≤ 7 }, Σ son todos los caracteres numéricos y caracteres especiales permitidos
(tales como .,+,-,E), F = {q1, q4, q5, q6}, y δ se expresa en el diagrama de transición de
la �gura 2.15, donde se observa el conjunto de caracteres N = {0,1,2,3,4,5,6,7,8,9}.
Figura 2.15: AF que reconoce un literal numérico en el lenguaje C
Se plantea como ejercicio pensar cómo puede modi�car el AF de la �gura 2.15 para reconocer
lo siguiente: cambiar el uso del punto para que en su lugar la coma (,) se utilice para separar
enteros y decimales, y el punto (.) se emplee como separador de las unidades decimales (co-
menzando desde el lado derecho de tres en tres). Por ejemplo, partes enteras de las literales
numéricas como: 1.300 o 35.413 o 38 o 23.300.080, etc.
Ejercicios propuestos
1. Para Σ = {0,1} construya un AFD que acepte los siguientes lenguajes:
a) El conjunto de cadenas que tiene 011 como subcadena.
b) El conjunto de todas las cadenas cuyo tercer elemento desde el extremo izquierdo
sea un 1.
c) El conjunto de cadenas en las que el número de ceros es divisible por 3.
d) El conjunto de cadenas que terminan con 01.
e) El conjunto vacío.
f ) El conjunto de la cadena vacía.
2. Constuya un AF para los siguientes lenguajes:
a) El conjunto de cadenas basadas en Σ={a,b,c} cuyo último símbolo no haya apare-
cido antes en la misma entrada.
36 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Cuadro 2.9: Tabla de transición δ
δ 0 1
→ p {p, q} {p}
q {r} {r}
r {s} ϕ
*s {s} {s}
Cuadro 2.10: Tabla de transición δ
δ 0 1
→ p {q, s} {q}
*q {r} {q, r}
r {s} {p}
*s ϕ {p}
b) Conjunto de 0 y 1 que contenga 2 ceros separados por un número de posiciones
múltiplo de 3. Nótese que 0 es un múltiplo de 3 válido.
3. Obtenga un autómata �nito (de cualquier tipo) para reconocer los siguientes lenguajes
apartir del alfabeto binario:
a) cadenas acabadas en 00
b) cadenas con dos unos consecutivos
c) cadenas que no contengan dos unos consecutivos
d) cadenas con dos ceros consecutivos o dos unos consecutivos
e) cadenas con dos ceros consecutivos y dos unos consecutivos
f ) cadenas acabadas en 00 o 11
g) cadenas con un 1 en la antepenúltima posición
h) cadenas de longitud 4
4. Construir un AFD equivalente a los siguientes autómatas:
a) M1 = ({p, q, r, s}, {0, 1}, δ, p, {s}) donde δ está dada por el cuadro 2.9
b) M2 = ({p, q, r, s}, {0, 1}, δ, p, {q, s}) donde δ está dada por el cuadro 2.10
c) M3 = ({p, q, r}, {a, b, c}, δ, p, {r}) donde δ está dada por el cuadro 2.11
d) M4 = ({q0, q1, q2, q3, q4}, {a, b}, δ, q0, {q4}) donde δ está dada por el cuadro 2.12
2.1. AUTÓMATAS DE ESTADOS FINITOS 37
Cuadro 2.11: Tabla de transición δ
δ λ a b c
→ p ϕ {p} {q} {r}
q {p} {q} {r} ϕ
*r {q} {r} ϕ {p}
Cuadro 2.12: Tabla de transición δ
δ a b λ
→ q0 {q1, q2} {q1, q3} ϕ
q1 ϕ ϕ {q3}
q2 {q4} ϕ ϕ
q3 ϕ {q4} ϕ
q4 ϕ ϕ ϕ
38 CAPÍTULO 2. LENGUAJES REGULARES Y AUTÓMATAS FINITOS
Bibliografía
[1] Alonzo Church: A note on the Entscheidungsproblem. Journal of Symbolic Logic. 1 (1936).
pp 40 - 41.
[2] Hopcroft, Rajeev Motwani, Je�rey D. Ullman. Introducción a la Teoría de Autómatas y
Lenguajes Formales. PrenticeHall, 2002.
[3] Chacín, M. y Padrón, J. (1994) Qué es teoría. Investigación y Docencia. Caracas: Publi-
caciones del Decanato de Postgrado, USR.
[4] Seymour Lipschutz (1970) Teoría de Conjuntos y Temas a�nes. macGraw-Hill
39