Teorı́a de la Computación 2011-1
Nota de Clase 1
Favio E. Miranda Perea
Facultad de Ciencias UNAM
9 de agosto de 2010
1. Fundamentos de la computación
Los fundamentos de la computación se dividen esencialmente en dos partes:
Teorı́a de la Programación: Dedicada a estudiar los lenguajes de programación, los cuales
nos sirven para implementar procesos de cómputo.
Teorı́a de la Computación: Dedicada a entender la naturaleza del cómputo, sus posibilida-
des y limitaciones.
1.1. Teorı́a de la Programación
Se divide en diversas disciplinas, como son:
Lógica Computacional.
Teorı́a de lenguajes de programación: paradigmas (lógico, funcional, imperativo, orientado
a objetos, etc), semántica operacional, tipado, etc.
Métodos formales: especificación y verificación
1.2. Teorı́a de la Computación
Mediante la teorı́a del cómputo, especificamente mediante la teorı́a de autómatas y lenguajes
formales, podemos tratar preguntas como:
¿Qué es un dispositivo de cómputo?
¿Qué se puede computar?
¿Qué no se puede computar?
¿Cual es el costo de un cómputo?
¿Qué se puede computar eficientemente?
¿Como clasificar un problema de acuerdo a su dificultad?
Al responder a estas preguntas, la teorı́a de la computación nos permitirá entender cuales
son las capacidades y limitaciones fundamentales de una computadora, debido a la captura de
las nociones de cómputo y computabilidad efectiva mediante abstracción matemática.
1
2. Abstracción del Concepto de Computadora
Una computadora es una máquina que transforma ciertos datos de entrada dados en re-
sultados o datos de salida.
Podemos pensar que una computadora es una función que transforma sus argumentos de
entrada en resultados.
¿ Cual serı́a el dominio de tal función? es decir, que tipos de datos se esperan como entrada:
números, palabras, textos, imagenes, etc.
¿ Cómo podemos representar los datos de entrada de manera uniforme ?
Cualesquiera datos de entrada para una computadora pueden ser codificados mediante una
cadena o sucesión de sı́mbolos.
¿Qué cadenas son aceptables como entrada ?
¿ Qué cadenas se obtienen como salida ?
¿Será posible caracterizar de manera finita a estos conjuntos de cadenas, los cuales pueden
ser infinitos?
3. Teorı́a de cadenas
Las cadenas son fundamentales para la mayorı́a de los sistemas formales. En esta sección
revisamos las operaciones de importancia entre cadenas.
Los sı́mbolos son los objetos más simples con los que trataremos. Una definición formal de
sı́mbolo nos llevarı́a al ámbito de la filosofı́a del lenguaje, ası́ que para nuestros propositos basta
decir que
Definición 1 Un sı́mbolo o caracter es una entidad considerada indivisible.
Ejemplos:
#, %, $, ←, ∧, a, 7
Por comodidad utilizaremos como sı́mbolos:
a,b,c,d,e,. . .
0,1,2,3,. . . , 9
Definición 2 Un alfabeto es un conjunto finito de sı́mbolos.
Ejemplos:
El alfabeto del español: a, b, c, d, e, f, . . . , z.
El alfabeto binario: 0, 1.
El alfabeto ASCII: a,. . . ,z,A,. . . , Z, $, %,#,. . .
Por lo general usaremos las letras griega Σ y Γ para denotar alfabetos.
2
Definición 3 Una cadena, expresión o palabra es una sucesión finita de sı́mbolos tomados de
un alfabeto dado Σ.
En otros ámbitos se permiten cadenas con un número infinito de sı́mbolos pero nunca en
nuestro curso.
Ejemplos:
En el alfabeto del español: abc, def, f eo, bonito, dsp, guajolote, uizcm.
En el alfabeto binario: 0, 101010, 00, 1100, 001, 11010.
Obsérvese que los sı́mbolos son a su vez cadenas que constan de un solo caracter. Más aún
la cadena vacı́a (i.e. la sucesión vacı́a de sı́mbolos) se denotará con el metası́mbolo ε1 . Este
metası́mbolo no es ni una palabra ni un sı́mbolo. Es decir estará prohibido considerar a ε como
sı́mbolo de un alfabeto Σ.
Definición 4 Al conjunto infinito de todas las cadenas sobre el alfabeto Σ se le denota con Σ?
y se le nombra la estrella o cerradura de Kleene2 de Σ. Es decir Σ? = {a1 . . . an | ai ∈ Σ}.
Las herramientas matemáticas fundamentales de nuestro curso son la recursión y la inducción
estructural. En el caso de Σ? la definición recursiva es:
ε ∈ Σ?
Si a ∈ Σ y w ∈ Σ? entonces wa ∈ Σ?
Son todas.
Esta definición recursiva genera el siguiente principio de inducción estructural:
Sea P ⊆ Σ? un conjunto de cadenas. Si ε ∈ P y ∀a ∈ Σ∀v ∈ P (va ∈ P ) entonces
∀u ∈ Σ? (u ∈ P )
Es decir, Σ? = P .
3.1. Operaciones con Cadenas
Definición 5 La longitud de una cadena w es el número de sı́mbolos en w y se define como
| · | : Σ? → N, Si w = a1 . . . an entonces |w| = n. Recursivamente:
|ε| = 0 ; |wa| = |w| + 1
Definición 6 La operación básica entre cadenas es la concatenación · : Σ? ×Σ? → Σ? y consiste
en pegar cadenas en orden de izquierda a derecha: Si v, w son cadenas entonces v · w será la
cadena obtenida al pegar v con w. Usualmente el operador · no se usa y escribimos simplemente
uv en vez de u · v
La concatenación puede definirse recursivamente como sigue: sean u, v ∈ Σ? , a ∈ Σ
uε = εu = u
1
Algunos autores denotan a la cadena vacı́a con λ o Λ.
2
Stephen Cole Kleene, 1909–1994, prominente lógico matemático.
3
u(va) = (uv)a
Ejemplos:
La concatenación de cala y baza es la cadena calabaza.
si v = broco y w = li entonces vw = brocoli.
si x = champu y y = rrado entonces yx = rradochampu.
Propiedades:
Asociatividad: (uv)w = u(vw).
Identidad: vε = εv = v.
Longitud: |vw| = |v| + |w|.
Además es claro que no es una operación conmutativa, por ejemplo jarrito 6= rritoja
Definición 7 La reversa de una cadena u, denotada uR , se define como sigue. Si u = a1 a2 . . . an
entonces uR = an an−1 . . . a2 a1 . La definición recursiva es (·)R : Σ? → Σ? .
εR = ε
(va)R = av R
Se cumplen las siguientes propiedades, que deben probarse mediante inducción estructural:
(uR )R = u
(uv)R = v R uR
3.2. Subcadenas, Prefijos y Sufijos
Decimos que v es una subcadena de u si existen cadenas x, y ∈ Σ? tales que u = xvy.
Un prefijo de u es una cadena v tal que u = vw para alguna cadena w ∈ Σ? . Se dice que
v es un prefijo propio si v 6= u.
Similarmente, un sufijo de u es una cadena v tal que u = wv para alguna cadena w ∈ Σ? .
Se dice que v es un sufijo propio si v 6= u.
Obsérvese que tanto ε como u son siempre sufijos y prefijos de u.
4. Los Conceptos Fundamentales
Los tres conceptos fundamentales en teorı́a de la computación son:
Lenguajes: conjuntos de cadenas.
Gramáticas: mecanismos para generar cadenas.
Autómatas: mecanismos para procesar cadenas.
Nuestro objetivo principal es estudiar las relaciones entre estos tres conceptos.
4
4.1. Gramáticas
Un mecanismo relevante para generar un lenguaje es mediante el concepto de gramática
formal.
Las gramáticas formales fueron introducidas por Chomsky en 1956
La intención era tener un modelo para la descripción de lenguajes naturales.
Posteriormente se utilizaron como herramienta para presentar la sintaxis de lenguajes de
programación y para el diseño de analizadores léxicos de compiladores
Volveremos a éllas más tarde.
4.2. Autómatas
Un autómata es una representación abstracta de una máquina
Los aspectos relevantes para nosotros son el diseño y la especificación de autómatas.
La abstracción captura únicamente el comportamiento de una máquina, es decir, las se-
cuencias de eventos que ocurren.
4.2.1. Un poco de historia
En su artı́culo “On Computable Numbers, with an Application to the Entscheidungs-
problem” de 1936,Turing reformula los resultados de Kurt Gödel de 1931 acerca de las
limitaciones de pruebas y cómputos, reemplazando el lenguaje formal universal de Gödel
con lo que hoy llamamos máquinas de Turing, que son un dispositivo formal y simple de
una computadora. El probo que tal máquina podrı́a der capaz de llevar a cabo cualquier
cómputo matemático concebible si este se representaba mediante un algoritmo.
En el artı́culo “A logical calculus of the ideas immanent in nervous activity” Bull. Math.
Biophysics 5 (1943), pp. 115-133, el neurofisı́ologo Warren McCulloch y el lógico Walter
Pitts, desarrollaron modelos de redes neuronales con ciclos de retroalimentación basados
en su visión de la neurologı́a. Este fue un intento para modelar la estructura de los nervios.
El modelo de Pitts-McCulloch fue simplificado por el lógico Stephen C. Kleene en 1956, en
el que se considera el primer artı́culo acerca de autómatas finitos y expresiones regulares,
“Representation of events in nerve nets and finite automata”.
En 1959 Rabin y Scott presentan una máquina con un número finito de estados que
simplifica a la máquina de Turing. For su artı́culo “Finite Automata and Their Decision
Problem” que introduce la idea de máquinas no deterministicas, un concepto invaluable.
Debido a este artı́culo ambos reciben el premio Turing en 1976.
En 1968 Ken Thompson usa la noción de expresión regular definida por Kleene en el
sistema UNIX,
4.2.2. Aplicaciones
Los autómatas tienen diversas aplicaciones en computación, por ejemplo:
Software para hallar patrones en una gran cantidad de texto, por ejemplo en colecciones
de páginas web.
5
Diseño de circuitos digitales.
Analizadores léxicos para compiladores.
Búsqueda de palabras clave en internet.
Verificación de sistemas con un número finito de estados (por ejemplo protocolos de co-
municación)
Verificación de modelos, modelado y verificación de sistemas empotrables (embebidos)
Aplicaciones en genética, patrones regulares en proteinas
Aplicaciones en lingüistica, construcción de diccionarios grandes, correctores de ortografı́a.
Modelado de máquinas reales: relojes, telefonos, seguros de auto, etc.
Modelado de sistemas discretos en general.
Existen diversos tipos de autómata, nosotros estudiaremos:
Autómatas con un número finito de estados: determinı́sticos, no determinı́sticos.
Autómatas de pila
Autómatas Linealmente Acotados
Máquinas de Turing.
Otras clases de autómatas que no estudiaremos aquı́ son los probabilı́sticos, celulares, paralelos,
de árbol, etc.
5. Lenguajes
Definición 8 Un lenguaje L sobre un alfabeto Σ es simplemente un conjunto de cadenas de Σ.
Es decir L ⊆ Σ? .
Si Σ = {m, u} entonces algunos lenguajes sobre Σ son:
L1 = {m, u} = Σ
L2 = {u, uu, uuu, uuuu, uuuuu, uuuuuu, . . .}.
L3 = {mu, um, mum, umu, mmu, ummm, mumumum}.
L4 = {mu, muu, muuu, muuuu, . . .}.
L5 = {m, mmm, mmmmm, . . . , m . . . , uuum, m . . .}.
Obsérvese que un lenguaje puede ser finito o infinito, que ∅ es un lenguaje, llamado lenguaje
vacı́o y que Σ? es un lenguaje llamado el lenguaje total. Además Σ y {ε} también son lenguajes.
5.1. Operaciones con Lenguajes
Dado que los lenguajes son conjuntos todas las operaciones conjuntistas son aplicables a
lenguajes. Si L, M ⊆ Σ? entonces
L ∪ M, L ∩ M, L − M, L̄ = Σ? − L
tambien son lenguajes.
6
5.1.1. Concatenación de Lenguajes
Al igual que en el caso de cadenas, podemos definir la concatenación entre lenguajes como
sigue:
LM = {uv | u ∈ L y v ∈ M }
Se cumplen las siguientes propiedades:
L∅ = ∅L = ∅
L{ε} = {ε}L = L
L(M N ) = (LM )N
L(M ∪ N ) = LM ∪ LN (M ∪ N )L = M L ∪ N L
5.1.2. Reversa de un Lenguaje
La reversa de un lenguaje se define como
LR = {uR | u ∈ L}
Se cumplen las siguientes propiedades:
(LR )R = L
(LM )R = M R LR
(L ∪ M )R = LR ∪ M R
(L ∩ M )R = LR ∩ M R
5.1.3. Cerradura de Kleene
La cerradura o estrella de Kleene de un lenguaje se define como
∞
[
L? = {u1 . . . un | ui ∈ L n ≥ 0} = Li
i=0
donde Li es la potencia i-ésima de L, definida como L = LL . . . L, i veces.
5.1.4. Cerradura Positiva
La cerradura positiva de un lenguaje se define como
∞
[
L+ = {u1 . . . un | ui ∈ L n > 0} = Li
i=1
7
5.1.5. Propiedades de los operadores de cerradura
Se cumplen las siguientes propiedades
L? = L+ ∪ {ε}
L? = L+ si y sólo si ε ∈ L.
(L? )? = L?
L? L? = L?
(L+ )? = (L? )+ = L?
(L+ )+ = L+
L+ L+ ⊆ L+
6. Lenguajes y Computadoras
Con el concepto de lenguaje podemos reformular las preguntas acerca de los datos de entrada
y salida en una computadora:
¿ Cual es el lenguaje de entrada de una computadora dada?
¿ Cual es el lenguaje de salida ?
¿ Serán estos lenguajes describibles finitamente?
7. Ejercicios
Martin: 1.38–1.47, 1.69–1.71, 2.34–2.37, 2.39–2.43, 2.59–2.66,
8
Teoria de la Computación 2011-I
Nota de Clase 6
Favio E. Miranda Perea
Facultad de Ciencias UNAM
24 de octubre de 2010
1. Preliminares
Las gramáticas formales fueron introducidas por Noam Chomsky en 1956 y son un mecanismo
relevante para generar lenguajes. La intención original era tener un modelo para la descripción
de lenguajes naturales pero posteriormente se han utilizado como herramienta para presentar la
sintaxis de lenguajes de programación y para el diseño de analizadores léxicos de compiladores.
1.1. Gramáticas Formales
Definición 1 (Gramática formal) Una gramática es una cuaterna G = hV, T, S, P i tal que:
V es un alfabeto cuyos elementos se llaman variables o sı́mbolos no-terminales, los cuales se
denotan con mayúsculas A, B, C, . . .
T es un alfabeto cuyos elementos se llaman sı́mbolos terminales, los cuales se denotan con
minúsculas a, b, c, . . .. Además se requiere T ∩ V = ∅.
S ∈ V es una variable distinguida llamada el sı́mbolo inicial.
P es un conjunto finito de reglas de reescritura, llamadas reglas de producción o simplemente
producciones. Cada regla de P es un par ordenado hα, βi tal que
• α ∈ (V ∪ T )⋆ − T ⋆ . Es decir, α es una cadena de sı́mbolos terminales ó no terminales,
con al menos un sı́mbolo no-terminal.
• β ∈ (V ∪ T )⋆ . Es decir, β es una cadena de sı́mbolos de V ∪ T , los cuales podrı́an ser
todos terminales.
• Usualmente en vez de escribir hα, βi ∈ P escribimos
α→β
y decimos que α produce a β, o que α se reescribe en β.
Las reglas de producción sirven para generar cadenas, proceso que se formaliza mediante el
concepto de derivación formal:
1
Definición 2 (Derivación) Dadas dos palabras w, v ∈ (V ∪T )⋆ decimos que v es derivable a partir
de w en un paso si y sólo si:
Existe una regla α → β en P y cadenas γ1 , γ2 ∈ (V ∪ T )⋆ tales que:
w = γ1 αγ2 y v = γ1 βγ2
y en tal caso escribimos w → v.
Algunos autores utilizan ⇒ en vez de → para denotar la relación de derivación. Nosotros
preferimos sobrecargar el operador →.
Decimos que una cadena v es derivable a partir de w si existen palabras γ2 , . . . , γn tales que
w = γ1 → γ2 . . . γn−1 → γn = v
En tal caso escribimos w →⋆ v. Obsérvese que en particular w →⋆ w.
Definición 3 (Lenguaje generado) Dada una gramática G = hV, T, S, P i definimos al lenguaje
generado por G, denotado L(G), como el conjunto de palabras de sı́mbolos terminales derivables
a partir del sı́mbolo inicial S. Es decir,
L(G) = {w ∈ T ⋆ | S →⋆ w}
1.2. Ejemplos
Veamos algunos ejemplos de gramáticas.
L = (a + b)⋆ . Cualquier cadena debe generarse.
• La cadena vacı́a debe generarse:
S→ε
• Si w ∈ L entonces wa ∈ L
S → Sa
• Si w ∈ L entonces wb ∈ L
S → Sb
• Ejemplo de derivación: w = ababb
S → Sb → Sbb → Sabb → Sbabb → Sababb → ababb
L = {ai bi | i ∈ N}
• Debe haber tantas aes como bes, es decir, si se agrega una a debe agregarse también una
b
S → aSb
• ε también debe generarse: S → ε
2
• Ejemplo de derivación w = aaabbb
S → aSb → aaSbb → aaaSbbb → aaabbb
L = {ai bj | i, j ∈ N, i ≤ j}
• La cadena vacı́a debe generarse (i = j = 0):
S→ε
• Debe haber al menos tantas bes como aes:
S → aSb
• Puede haber más bes:
S → Sb
• Ejemplo de derivación w = aaabbbbb
S → aSb → aaSbb → aaaSbbb → aaaSbbbb → aaaSbbbbb → aaabbbbb
L = {ai bj aj bi | i, j ∈ N}
• Primero generamos el centro de la palabra, bj aj :
S → C C → bCa C → ε
• Después los extremos ai , bi :
S → aSb
• Ejemplo de derivación w = a2 b3 a3 b2 = aabbbaaabb
S → aSb → aaSbb → aaCbb → aabCabb → aabbCaabb
→ aabbbCaaabb → aabbbaaabb
L = {ai bi aj bj | i, j ∈ N}
• Ya vimos que el lenguaje {ai bi | i ∈ N} se genera mediante:
P →ε P → aP b
• Para generar a L simplemente agregamos:
S → PP
• Ejemplo de derivación w = a3 b3 a2 b2 = aaabbbaabb
S → P P → aP bP → aaP bbP → aaaP bbbP → aaabbbP → aaabbbaP b →
aaabbbaaP bb → aaabbbaabb
3
L = {ai bi | i ∈ N} ∪ {bi ai | i ∈ N}
• El lenguaje {ai bi | i ∈ N} se genera mediante:
P →ε P → aP b
• El lenguaje {bi ai | i ∈ N} se genera mediante:
Q→ε Q → bQa
• Para generar a L simplemente agregamos:
S→P S→Q
Para definir una gramática G = hV, T, S, P i en la mayorı́a de los casos será suficiente con nombrar
sus producciones. Para lo cual se puede utilizar la notación de disyunción |, Si hay producciones de
la forma Q → β1 , . . . , Q → βn esto se escribe de la forma
Q → β1 | β2 | . . . | βn
2. Jerarquı́a de Chomsky
De acuerdo a la forma de sus reglas de producción una gramática se clasifica en diversas clases.
Esta clasificación se conoce como Jerarquı́a de Chomsky, puesto que fue introducida por Noam
Chomsky.
2.0.1. Gramáticas Recursivamente Enumerables o de tipo 0
Son todas las gramáticas formales. Como no hay restriccion alguna en la forma de las reglas de
producción pueden incluirse reglas de producción de la forma
α→ε
Tales gramáticas son capaces de borrar cadenas y se les conoce como gramáticas contraibles.
Por ejemplo:
aS → bSb, aSb → ε, SbS → bcS
Más adelante veremos porque se les nombra recursivamente enumerables.
2.0.2. Gramáticas Dependientes del Contexto o de tipo 1
Son aquellas gramáticas con todas sus producciones de la forma
α1 Aα2 → α1 βα2
donde
α1 , α2 ∈ (V ∪ T )⋆
A∈V
4
β 6= ε.
Con la posible excepción de la regla S → ε, en cuyo caso se prohibe la presencia de S a la derecha
de las producciones.
Una gramática de esta forma se conoce como gramática dependiente del o sensible al contexto.
Por ejemplo la siguiente gramática dependiente del contexto genera al lenguaje L = {ai bi ci | i ≥
0}
S → A A → aABC | abC CB → BC
bB → bb bC → bc cC → cc
2.0.3. Gramáticas Libres de Contexto o de tipo 2
Son aquellas gramáticas con todas las producciones de la forma
A→α
donde
A∈V
α ∈ (V ∪ T )⋆ .
Obsérvese que la definición incluye a la regla S → ε. Estas gramáticas se conocen como gramáticas
libres o independientes del contexto. La mayorı́a de las gramáticas para lenguajes de programación
caen en esta categorı́a.
Algunos ejemplos son:
L = {an bn | n ∈ N} que no es regular
S → aSb | ε
L = {w ∈ {a, b}⋆ | w = wR } que no es regular
S → aSa | bSb | a | b | ε
L = {an bam | n, m ≥ 1} = a⋆ ba⋆
S → aS | aB
B → bC
C → aC | a
2.0.4. Gramáticas Regulares o de tipo 3
Son aquellas gramáticas llamadas lineales, las cuales pueden ser:
Lineales por la derecha: todas las producciones de la forma
A → aB A → a A → ε
con A, B ∈ V, a ∈ T
5
Lineales por la izquierda: todas las producciones de la forma
A → Ba A → a A → ε
con A, B ∈ V, a ∈ T
Es importante recalcar que no se permite mezclar ambos tipos de producciones. Es fácil ver que toda
gramática lineal por la izquierda es equivalente a una gramática lineal por la derecha de manera
que no hay pérdida de generalidad en usar solamente gramáticas lineales por la derecha.
Como ejemplo tenemos:
S → aS | bC
C → bC | aS | ε
De hecho L(G) = (a + b)⋆ b.
Definición 4 (Tipo de un lenguaje) Decimos que un lenguaje es de tipo i si y sólo si la gramáti-
ca con mayor ı́ndice que lo genera es de tipo i. Es decir, un lenguaje es de tipo i si existe una
gramática de tipo i que lo genera y no existe un gramática de tipo j > i que lo genere.
Las siguientes observaciones son importantes:
Si un lenguaje es de tipo i también podemos referirnos a él con el nombre especı́fico del tipo,
por ejemplo un lenguaje de tipo 2 es un lenguaje libre de contexto, etc.
La jerarquı́a de gramáticas origina una jerarquı́a en los lenguajes generados:
L3 ( L2 ( L1 ( L0
La jerarquı́a de Chomsky permite refinar la teorı́a de la computación clasificando lenguajes
en función de los recursos computacionales necesarios para reconocerlos.
Obsérvese que si una gramática no es de cierto tipo no es posible afirmar que el lenguaje
generado por élla tampoco lo sea. Por ejemplo la siguiente gramática G no es de tipo 3
(regular)
S → A1A1A
A → 0A | ε
pero el lenguaje generado por élla sı́ lo es al existir una gramática regular G′ equivalente es
decir L(G) = L(G′ ):
S → 0S | 1A
A → 0A | 1B
B → 0B | ε
De hecho L(G) = L(G′ ) = 0⋆ 10⋆ 10⋆ .
6
3. Lenguajes y Gramáticas Regulares
La definición de lenguaje de tipo 3 aparentemente proporciona una nueva clase de lenguajes
regulares. Ahora veremos que no hay peligro ni ambigüedad, un lenguaje tipo 3 es también un
lenguaje regular en el sentido de autómatas y expresiones regulares y viceversa.
Proposición 1 (AF ⇒ GR) Dado un AF M = hQ, Σ, δ, q0 , F i existe una gramática regular G =
hV, T, S, P i tal que L(M ) = L(G). Es decir, todo lenguaje regular es generado por una gramática
regular.
Demostración. Sin pérdida de generalidad suponemos que el autómata no tiene ε-transiciones.
Definimos la gramática G como sigue:
V := Q
T := Σ
S := q0
El conjunto de producciones P se define como sigue:
• Si p ∈ δ(q, a) entonces agregamos q → ap a P .
• Si qf ∈ δ(q, a) con qf ∈ F entonces agregamos q → a.
Se deja al lector verificar que L(M ) = L(G). ⊣
Por ejemplo, para el autómata M dado por:
0 1
q0 1 q1
1
0
0 q2
La gramática obtenida es:
q0 → 0q0 | 1q1 q1 → 1q1 | 0q2 | 0 q2 → 0q0 | 1q1
a
Para el autómata M :
b
q0 q1
a
b
b
a
q2
la gramática generada es:
7
q0 → aq0 | bq1 | a | b q1 → aq0 | bq2 | a q2 → aq0 | bq1 | a
Proposición 2 (GR ⇒ AF) Dada una gramática regular G = hV, T, S, P i existe un autómata
finito M = hQ, Σ, δ, q0 , F i tal que L(M ) = L(G). Es decir todo lenguaje generado por una gramática
regular es un lenguaje regular.
Demostración. Sin pérdida de generalidad sea G una gramática lineal derecha. Definimos a M
como sigue:
Q := V ∪ {qf }
Σ := T
q0 := S
F := {qf }
La función de transición δ se define como sigue:
• Si A → aB ∈ P entonces B ∈ δ(A, a).
• Si A → a ∈ P entonces qF ∈ δ(A, a).
• Si A → ε ∈ P entonces qF ∈ δ(A, ε).
Queda como ejercicio probar que L(G) = L(M ). ⊣
La gramática regular para L = 0⋆ 10⋆ 10⋆ .
S → 0S | 1A
A → 0A | 1B
B → 0B | ε
0 0
genera el siguiente autómata:
1
S A
1
0 ε
B qf
La gramática
S → aS | aB | b
B → bC
C → aC | a
8
genera el siguiente autómata
a
a
S B
b b
a
qf C
a
