Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
lenguajes,gramticasyautmatas unenfoqueprcticuceldad - Franco Corts-Romeo
Desafío COL y ARG Veintitrés
Compartir
Vista previa del material en texto
lENGUAJES,GRAMÁTICAS y AUTÓMATAS
. UN ENFOQUE PRÁCTICO
~
I
LENGUAJES, GRAMÁTICAS
" y AUTOMATAS
UN ENFOQUE PRÁCTICO
Pedro Isasi Viñuela
Paloma Martínez Fernández
Daniel Borrajo Millán
Universidad Carlos III de Madrid
..
TT
ADDISON-WESLEY
Harlow, Inglaterra • Reading, Massachusetts • Menlo Park. Californ ia • Nueva Yo -
Don Mills, Ontario • Amsterdam • Bonn • Sydney • Singapur
Tokio • Madrid • San Juan • Milán • México • Seúl • Taipei
~--------------------------------------------------------~
[lustración de la cubierta: Wassily Kandinsky, 1929.
Pisos.
© 1997, por Addison·Wesley Iberoamericana España, S.A.
Reservados todos los derechos.
No está permitida la reproducción total o parcial de este libro, ni su tratamiento informático ni la transmi-
sión de ninguna forma o por cualquier medio, ya sea electrónico, por fotocopia, por registro u otros méto-
dos, sin el permiso previo y por escrito de los titulares del copyrighl.
ADDISON·WESLEY IBEROAMERICANA
Malabia 2362-2.° G, Buenos Aires, Argentina.
Cruz 1469-dpto. 21, Independencias, Santiago de Chile.
Apartado aéreo 241-943, Bogotá, Colombia.
Espalter 3,28014 Madrid, España.
I Jacob Way, Reading, Massachusetts 01867, E.U.A.
Apartado postal 22-012, México DF, México.
Jr. San Antonio Este, n.O 658. dpto. D, Urb. Ventura Rossi .
25 Lima, Perú.
El Monte Mall, 2.° piso, oficina 19-B. Ave. Muñoz Rivera.
HalO Rey. 009 I 8 Puerto Rico.
Apartado Postal 5 I 454. Caracas 1050 A. Venezuela.
Impreso en España. ¡'rin/eel ill S/will.
ISBN: 0-201 -65323-0
ISBN: 84-7829-014-1
Depósito legal: M. 36.039-1997
I 2 3 4 5 6 78 9 O - CO - 01 00 99 98 97
A Ana, Juan Miguel y a Isabel
- -- - --- -- --- -------------------"--------~
Agradecimientos
Los autores agradecen a .-\raceli anchis las correcciones realizadas a ver-
siones anteriores del libro. a Julio García del Real por su valiosa ayuda en
la preparación y ~ truc ' uración de la asignatura . as í como a los revisores
del libro por sus coment~ios .
- _--...
Prefacio
Los fundamentos teóricos de la informática, que han dado en llamarse In-
formática Teórica, provienen de diferentes ramas del conocimiento. Este
aspecto, unido a la fuerte componente teórica que esta disciplina requie-
re, como no podría ser de otra forma, hace que a menudo los textos de
Informática Teórica sean difíciles de leer. Sin embargo, detrás de toda es-
ta componente teórica se esconde una disciplina amena, muy instructiva y
con grandes posibilidades de aplicación. Todo esto queda a menudo oculto
entre definiciones, teoremas y demostraciones. Este libro pretende ser una
manera de superar este escollo. No pretende ser una sustitución de otros
textos con mayor contenido teórico, sino más bien un complemento a los
mismos. Todos los temas han sido tratados con el rigor exigible, aún cuan-
do no aparezca una fuerte carga de teoremas y demostraciones. De esta
forma, puede constituir un libro ideal para iniciarse en los temas tratados,
o una guia rápida de consulta de los diferentes contenidos. En cualquier
caso, se trata de un texto autocontenido y que no exige de conocimientos
previos por parte del lector para su comprensión.
Por otra parte, tiene un alto contenido práctico, entendido como un
gran número de ejercicios, en los que reflejar y complementar los conte-
nidos teóricos. Creemos, desde nuestra perspectiva de la docencia de la
asignatura que abarca estos temas en la universidad, que la mejor forma
de comprender y asentar los conocimientos es con la práctica. Afortuna-
damente, las materias de la Informática Teórica son muy versátiles a la
hora del planteamiento de ejercicios, y estos sirven de apoyo fundamental
e imprescindible al texto. Es por esto que hemos querido que en el título
apareciera explícitamente "un enfoque práctico", para resaltar el hecho de
que se trata de un libro con dos partes diferenciadas; por un lado se trata de
un libro de teoría autocontenido, y, por otro, un libro de ejercicios comple-
to. Esto queda remarcado por el hecho de que los ejercicios aparecen todos
juntos al final de cada capítulo, como si de otro capítulo independiente se
tratase. Por último, hemos querido añadir un capítulo de aplicaciones, pa-
ra mostrar algunos de los numerosos campos en 1 que se pueden utilizar
estos conceptos.
Pedro .. Paloma :\lartínez. y Daniel Borrajo
~an ' . Sept iembre de 1997
,
Indice General
1 Introducción 1
1.1 Lenguajes, Gramáticas y Autómatas 1
1.2 Estructura del libro . 5
1.3 Notaciones 6
2 Lenguajes y Gramáticas Formales 7
2.1 Lenguajes .. 7
2.1.1 Definiciones básicas 7
2.1.2 Operaciones con palabras 8
2.1.3 Operaciones con lenguajes . 9
2.1.4 Otras definiciones 11
2.2 Gramáticas formales 13
2.2.1 Definiciones . 13
2.2.2 Tipos de Gramáticas 16
2.2.3 Árboles de derivación 19
2.2.4 Ambigüedad 20
2.2.5 Recursividad 21
2.2.6 Factorización a izquierdas 25
Ejercicios 27
3 Gramáticas Regulares y Autómatas Finitos 43
3.1 Gramáticas regulares. 43
3.2 Máquinas Secuenciales 46
3.2.1 Definición . 46
3.2.2 Representación 49
3.2.3 Extensión a palabras de la entrada y salida 51
3.2.4 Equivalencia de Máquinas Secuenciales. 55 ·
. \
3.2.5 Equivalencia de Máquina de Mealy y
Máquina de Moore 61
3.3 Autómatas Finitos Deterministas (AFD) 63
3.3.1 Definición . 63
3.3.2 Representación de un AFD 65
3.3.3 Conceptos relativos a AFDs 66
3.3.4 Equivalencia de AFD 68
3.4 Autómatas Finitos No Deterministas (AFND) 75
3.4.1 Definición 75
3.4.2 Representación 76
3.4.3 Conceptos asociados a AFNDs 77
3.4.4 Autómata Finito asociado a una G3 81
3.5 Expresiones regulares (ER) 83
3.5.1 Definiciones . 83
3.5.2 Teoremas de Kleene 85
3.6 Autómatas de Células de McCulloch-Pitts 97
3.6.1 Definición 97
3.6.2 Representación 98
3.6 .3 Construcción de un AF equIvalente . 101
3.6.4 Construcción de un Autómata de Células equivalente
a un AF . 106
3.7 Autómatas probabilísticos 107
3.7.1 Definición 108
3.7.2 Matrices de probabilidad de transición 108
3.7.3 Vectores de estados. 109
3.7.4 Lenguaje aceptado por un AFP . 111
3.7.5 AF como AFP 113
Ejercicios 115
_" 4 Gramáticas Independientes del Contexto y Autómatas a
Pila 237
4.1 Gramáticas Independientes del Contexto . 237
4.1.1 Definiciones. .. .... . ... .. 237
4.1.2 Forma Normal de Chomsky (FNC) 242
, 4.1.3 Forma Normal de Greibach (FNG) 246
. 4.2 Autómatas a Pila (AP) 248
4.2.1 Definición...... . . 248
4.2.2 Movimientos .. ... .
4.2.3 Descripción instantánea
251
254
4.2.4
4.2.5
4.2.6
Ejercicios
Autómatas a Pila Deterministas ... . .
Lenguaje aceptado por un AP ..... .
Autómatas a Pila y Gramáticas de tipo 2
5 Gramáticas y autómatas generales
5.1 Máquinas de Turing
5.1.1 Definición ......... .
255
256
257
263
321
321
321
5.1.2 Movimiento. .. ...... 323
5.1.3 Lenguaje reconocido por una Máquina de Turing 326
5.1.4 Variantes de las Máquinas de Turing . 326
5.1.5 Máquina de Turing Universal (MTU) 327
5.1.6 Máquinas de Turing y computación 329
5.2 Autómatas Linealmente Acotados. 330
Ejercicios ..
6 Aplicaciones
6.1 Construcción de compiladores
6.1.1 Analizador Léxico ..
~ 6.1.2 Analizador Sintáctico
6.2 Análisis del lenguaje natural.
6.3 Aplicaciones de Control
6.4 Más aplicaciones . . . . . . .
331
343
343
346
351
357
368
372
Capítulo 1
INTRODUCCIÓN
Puesto que este libro abarca la Teoría de Gramáticas, Lenguajes y Máquinas
Abstractas (Autómatas) , en esta introducción se comenzará aclarando el
significado de cada uno de los conceptos y la relación existente entre ellos.
A continuación, se describirá la estructura del libro y algunas aclaraciones
sobre la notación empleada a lo largo del texto.
1.1 Lenguajes, Gramáticas y Autómatas
Toda comunicación involucra la utilización de un lenguaje. Así, por ejem-
plo, las personas se comunican con el resto en los diferentes idiomas (len-
guajes naturales) o con las máquinas (lenguajes artificiales) a través deconjuntos de símbolos. Se define lenguaje como un conjunto de palabras,
también llamadas cadenas o sentencias, que están formadas por símbolos
de un alfabeto. Así, por ejemplo, el idioma español está formado por un
conjunto de palabras compuestas por letras (símbolos) del alfabeto español.
Una gramática da cuenta de la estructura de un lenguaje, es decir , de las
sentencias que lo forman, proporcionando las formas válidas en que se pue-
den combinar los símbolos del alfabeto. En el caso del español, las oraciones
deben ajustarse a una gramática. Una consideración importante es la dis-
tinción entre lenguajes formales, que son los que se tratarán en este libro, y
lenguajes naturales (inglés, español, etc.). Se puede decir que la diferencia
estriba en que los lenguajes formales (como pueden ser los lenguajes de
1
programación) obedecen a reglas prees ab
ellas , no evolucionan y han sido cread
go, los lenguajes naturales (utilizad T
las reglas gramaticales que rigen su """-mm .,...,,
posterioridad para explicar e ta úl ÍI!la.
recibir y transmitir información.
nas de símbolos que se le p """...L.>oOo-
o cadenas de símbolos a ~
contienen la información naresane
entrada, cuál será el ~""''"'-U-'1U~1I
conexión que e. e e
sobre gramá ieas y m<>.ql~~ a.b~U1~a"
describe
genera
CLenguaE)
genera
Figura 1.1: Conexiones entre los conceptos de lenguaje. !!TaIIlá: y
autómata.
El concepto de gramática procede de los estudios de Cho IT
búsqueda de una descripción formalizada de las oraciones de un le
turaL Chomsky clasificó las gramáticas en cuatro grandes grup
G2, G3) cada uno de los cuales incluye a los siguientes ( G3~G2~G 1 =GO .
Las gramáticas Tipo Ü se denominan gramáticas sin restriccion o
máticas de estructura de frases; las gramáticas Tipo 1 se denominan _ , i-
bIes al contexto; las gramáticas Tipo 2 se conocen como gramáticas in
pendientes del contexto y, por último, las gramáticas Tipo 3 denominan
gramáticas regulares. Cada tipo añade restricciones al tipo inmedia¡ame
te superior y la jerarquía va desde la más general a la más restricti\a . Cada
una de estas gramáticas es capaz de generar un tipo de lenguaje. e n 1 n-
guaje L se llama del tipo i (i=ü, 1, 2, 3) si existe una gramática G del ipo
i capaz de generar o describir ese lenguaje.
Estos estudios previos sobre teorías de gramáticas formales y le ~j ::.
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN E NFOQUE PRÁCTICO 3
crearon las bases de la lingüística matemática, la cual tendría aplicación
no solo al estudio del lenguaje natural sino también a los lenguajes forma-
les. Así, los lingüistas distinguen entre gramática particular (propiedades
de lenguajes concretos o artificiales) y gramática universal (propiedades
generales que pueden aplicarse a cualquier lenguaje humano).
La teoría de los autómatas proviene del campo de la ingeniería eléctrica.
Shannon publicó varios trabajos donde demostraba la aplicación de la lógica
matemática a los circuitos combinatorios y secuenciales. Posteriormente,
sus ideas se desarrollaron para dar lugar a la Teoría de Autómatas. Mo-
ore publicó el primer estudio riguroso sobre autómatas y, a finales de los
años 50, se comenzó a ver la utilidad de los autómatas en relación con los
lenguajes.
La teoría de lenguajes y gramáticas formales tiene una relación directa
con la teoría de máquinas abstractas, siendo posible establecer entre ambas
un isomorfismo. Dado que las gramáticas proporcionan las reglas utilizadas
en la generación de las cadenas de un lenguaje, se puede establecer una co-
nexión entre la clase de lenguajes generados por ciertos tipos de gramáticas
y la clase de lenguajes reconocibles por ciertas máquinas. Así, se pueden
identificar los lenguajes del tipo O con la clase de lenguajes reconocidos por
una Máquina de Turing; los lenguajes del tipo 1 con los Autómatas Line-
almente Acotados; los lenguajes de tipo 2 con los Autómatas a Pila y, por
último, los lenguajes de tipo 3 con los Autómatas Finitos, los Autómatas
Probablísticos y los Autómatas de Células de McCulloch-Pitts. Al igual
que ocurría con las gramáticas, cada tipo de máquina abstracta añade res-
tricciones al tipo de máquina del nivel superior. Todas poseen una cinta de
donde leen los símbolos de entrada, un conjunto de estados que represen-
tan diferentes fases del análisis de las palabras de entrada, un lugar donde
generar la salida, y, en algunos casos, cuentan con dispositivos auxiliares de
memoria. Las diferencias entre ellas estriban en la capacidad para escribir
en la cinta de entrada, en los distintos tipos de movimientos que pueden
realizar sobre la cinta, si tienen o no memoria auxiliar, etc.
Establecidas las reglas de una gramática, una cadena de símbolos perte-
necerá al correspondiente lenguaje si tal cadena se ha formado obedeciendo
esas reglas. A partir de una gramática se puede construir una máquina
reconocedora o aceptadora del lenguaje generado por esa gramática, de tal
forma que cuando reciba a su entrada una determinada cadena de símbolos
indicará si dicha cadena pertenece o no al lenguaje. Una máquina reconoce
un lenguaje L si es capaz de reconocer todas las sentencias pertenecientes a
L y de no reconocer ninguna sentencia que no pertenezca a L. La figura 1.1
4 CAP ' o .
muestra la relación existente entre los
que una gramática describe formalmeme un ~.7""'r,:I¡. j€
puede ser reconocido o aceptado por una OOiamJc:Jaca r:lCSIq:::IDa G.lS~n:a
o autómata, entonces es posible establecer-
abstractas y gramáticas tal y como ~
Gramática
Tipo O: Gramática
sin Restricciones
Tipo 1: Gramática
Sensible al Contexto
Tipo 2: Gramática
de Conte:\,o Libre
Tipo 3: Gramá ¡ca
R~ar
Regular
Autómata Linealm €
Acotado (ALA
Autómata a Pila
(AP)
Autómata Fini o
(AF)
Tabla 1.1: Relación entre lenguaje, gramática y autómata.
La teoría de gramáticas y máquinas teóricas tiene múltiples aplicacio-
nes en diversas áreas de conocimiento. Algunos ejemplos de las aplicacio-
nes de los lenguajes regulares y los autómatas finitos son los analizador
léxicos que se utilizan en los compiladores de lenguajes de programació .
Normalmente, un analizador léxico es un autómata que se utiliza para el
reconocimiento de las palabras empleadas en un lenguaje de programación
(variables, palabras reservadas, números, etc.). También se ut ilizan en 1 -
editores de texto para buscar y reemplazar palabras que se equiparan con
una expresión regular.
La sintaxis de los lenguajes de programación (Pascal, C. etc. ) está d
crita mediante gramáticas de Tipo 2 (independientes del contexto) aunque
también pueden contener algunos aspectos que requieran de una gramá ica
sensible al contexto.
En cuanto a las Máquinas de Turing, se corresponden con las gramá icas
sin restricciones. La peculiaridad de este tipo de gramáticas es que puede
describir cualquier suceso computable. Un suceso computable es aquél que
mediante un procedimiento es capaz de transformar unas determinadas
entradas en las salidas requeridas. Ésta es precisamente la capacidad que ~
necesita en un computador; el poder describir un procedimiento (pro!mUll.a l
que, a partir de unas entradas, sea capaz de producir una salida . í
pues, existe una asociación entre las Máquinas de Turing y los fenómen
computables, de forma que se dice que un suceso es computable i ~. e
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 5
una Máquina de Thring capaz de describirlo.
1.2 Estructura del libro
El texto del libro trata de seguir esta misma estructura, y así está dividido
en los siguientes capítulos:
Capítulo 2 Se tratan los conceptos fundamentales que serán empleados
a lo largo del resto del texto como son los lenguajes y las gramáticas.
Capítulo 3 Siguiendo la división de Chomsky, se tratan los temas re-
lacionados con las gramáticas tipo 3 y las máquinas reconocedoras de los
lenguajes tipo 3, autómatas finitos , tanto en su versión determinista, como
no determinista. Se tratan,también, las máquinas secuenciales que per-
miten, no sólo reconocer, sino generar una salida correspondiente a una
determinada entrada. También se describen las expresiones regulares, que
permiten representar de forma sencilla y compacta los lenguajes regula-
res. Por último, se incluyen varios tipos de autómatas finitos, como son los
autómatas probabilísticos y los autómatas de células de McCulloch-Pitts .
Capítulo 4 Se dedica a las gramáticas de tipo 2, independientes del
contexto, y las máquinas reconocedoras de los lenguajes de este tipo de
gramáticas, los autómatas a pila. La importancia que tienen estos lenguajes
es que son los más utilizados para describir los lenguajes de programación
de alto nivel.
Capítulo 5 Se presentan las gramáticas de tipo O y 1 y las máquinas de
Thring como dispositivos de cómputo universal y reconocedoras de lengua-
jes de gramáticas sin restricciones.
Capítulo 6 En este capítulo se realiza una breve descripción de algunas
de las diferentes líneas de aplicación de los conceptos tratados en el libro.
Así, se presentan ejemplos de sistemas reales cuyo diseño fundamental está
completamente ligado a los conceptos teóricos descritos en el libro.
6
1.3 Notaciones
El libro asume el conocimiento, por parte del
básica matemática. En un breve resumen .
ciones:
• Conjunto: {xl ... }, significa el conjunto e
• Pertenencia: x E ~ , significa que el eleme o :: -=>,....;.-,-.:!:--. .~c::::I~r::::::;;b
~.
• Inclusión: G ~ G', significa que el conjun o e
G' .
• Cardinalidad: IGI , representa el número de clem!E::~
G.
• Unión de conjuntos: G U G' , significa la unión de los conjuntos e y
G' .
• Intesección de conjuntos: G n G' , significa la intersección de los con-
juntos G y G' .
• Simplificación de notación de elementos de conjunto: a .. z ó a, . ... z .
significa todas las letras entre a y z.
• Aplicación entre conjuntos: f : El X E 2 X . .. x En ~ SI X S2 X ... X Sm·
significa que la función f (aplicación) está definida entre los conjuntos
Ei y los conjuntos Sj. También se puede entender desde el punto de
vista computacional como que recibe a la entrada un elemento de
cada uno de los conjuntos Ei y genera como salida un elemento de
cada uno de los conjuntos Sj.
• Definición: Concepto, notación: . . . , significa que la definición del
concepto cuya notación aparece después de la coma es lo que aparece
después de los dos puntos.
Capítulo 2
LENGUAJES y GRAMÁTICAS
FORMALES
Este capítulo describe los elementos básicos de la Informática Teórica: los
lenguajes y gramáticas formales. Dentro de las gramáticas, se estudia la .
clasificación más clásica de gramáticas, que sirve de hilo conductor para el
resto de capítulos.
2.1 Lenguajes
En esta sección se tratarán los temas relacionados con lenguajes formales.
Se verán algunas definiciones y operaciones que se pueden realizar con las
palabras de un lenguaje, así como con los propios lenguajes.
2.1.1 Definiciones básicas
• Alfabeto, ~: conjunto no vacío finito de símbolos (letras, números,
combinaciones de letras y números , ... )
Ejemplos:
el alfabeto español, el inglés, el alfabeto de los números, el alfabe-
to formado por todos los símbolos del teclado de un ordenador, el
alfabeto formado por los cuatro símbolos {na,pa,la, bra}
7
•
8 CAPÍTULO 2. LENGUAJES y G
• Palabra ° cadena: secuencia finita de SJu 'unOO!(jE
Ejemplos:
"palabra", "word", "1234", "alfa-?23!", "napa-
• Longitud de una palabra, Ixl: dada una palabra I C:~ ]l'C:ec:a
símbolos de un alfabeto ~, su longitud es el número de . 1
alfabeto que la forman.
Ejemplos:
Ipalabral=7 en el caso de que los símbolos sean los del alfabe
Si ~l = {na,pa,la,bra}, la longitud de la palabra palabra seria 3_
• Palabra vacía, A: palabra de longitud O (IAI = O); es decir. _ I
contiene ningún símbolo
• Universo de un alfabeto, W(~): todas las palabras que se puro
formar con símbolos del alfabeto~ . Contiene un número infini o dE'
elementos (palabras). La palabra vacía pertenece a todos los unÍn:'r-
sos.
Ejemplo: W (~d = {A, na,pa,la, bra, nana, napa, nala, nabra .. . . }
• Lenguaje sobre un alfabeto, L(~): es todo subconjunto de W ( ~ ) .
Como el universo asociado a un alfabeto es infinito, hay infinitos
lenguajes asociados a un alfabeto.
Ejemplos:
Dos posibles lenguajes de ~l serían:
Ll (~d = {nana,napa,lana}, y
L2(~1) = {A,nana,pana,palabra,papa,pala} .
2.1.2 Operaciones con palabras
• Concatenación: si x e y son palabras, la concatenación. x · y . una
palabra formada por los símbolos de x seguidos de los símbolos de y .
Muchas veces, se representará simplemente como xy.
Ejemplo: En ~l, si x =pa e y =labra, x . y =palabra
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 9
. .
• Potencia: la potencia i-ésima de una palabra x, x\ se forma por la
concatenación i veces de X; xi = 1 . x . ,: ... :z;,.
Por definición, para toda palabra x, se cumple: xO = A
Ejemplo: En I: I , si x = pala, x2 =palapala
Si I:2 = {O, 1} Y x = 01, x 3 = 010101
• Reflexión: si la palabra x está formada por los símbolos Al, A2, .. . , An,
entonces la palabra inversa de x, x- 1, se forma invirtiendo el orden
de los símbolos en la palabra; x- 1 = An ... A2Al'
Ejemplo: En I:1 , si x = pala, x- 1 =lapa
En I:2 , si x = 01 , x- l = 10
2.1.3 Operaciones con lenguajes
• Unión: si LI y L 2 son lenguajes, su unión, LI U L 2 , contendrá todas
las palabras que pertenezcan a cualquiera de los dos lenguajes;
Ejemplo: Si LI (I: I ) = {nana, napa, lana}, y
L 2 (I: I ) = {A,nana,pana,palabra,papa,pala} ,
Ll (I: I )UL2 (I:¡) = {A ,nana,napa,lana,pana,palabra,papa,pala}
• Intersección: si Ll y L 2 son lenguajes, su intersección, LI n L 2 ,
contendrá todas las palabras que pertenezcan a los dos lenguajes;
Ejemplo: Si LI(I: I) = {nana,napa,lana} , y
L 2 (I:1) = {A , nana,pana,palabra,papa,pala} ,
L¡(I: I ) n L 2 (I: I ) = {nana}
10 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F Oru.L -~
• Resta: si Ll y L2 son lenguajes, la resta de L l y 0 - L: - L·2 ·
contendrá todas las palabras que pertenezcan a Ll y no pen ezca..n
a L 2 ;
Ejemplo: Si L1(¿;1) = {nana,napa,lana}, y
L 2 (¿;l) = {A, nana,pana,palabra,papa,pala} ,
L1(¿;1) - L2 (¿;1) = {napa,lana} , y
Ld¿;l) - L1(¿;d = {A,pana,palabra,papa,pala}.
• Concatenación: dados dos lenguajes Ll y L2 , su concatenación.
Ll . L2 , contendrá todas las palabras que se pueden formar por la
contenación de una palabra de Ll y otra de L2 ;
Ejemplo: Dados Ll (¿;l) y L2 (¿;t},
Ll (¿;t}·L2(¿;1) = {nana,napa,lana,nananana,napanana .. . . }
• Potencia: la potencia i-ésima de un lenguaje corresponde a la con-
catenación i veces del lenguaje con él mismo;
Por definición, para todo lenguaje L i , se cumple: L? = {A}
Ejemplo: Si Ll (¿;2) = {O, 1}, entonces Lr(¿;2) = {00, 01. 10. 11}
• Clausura positiva:
La clausura positiva de un lenguaje L se forma por la Uillon
de todas las potencias del lenguaje, excluyendo la potencia O:
L+ = U~l L i
'.
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 11
Ejemplo: Si Ll(~2) = {O, 1} ,
entonces Ll (~2)+ = {O, 1,00, 01 , 10, 11,000,001, ... }
La clausura positiva de cualquier alfabeto (considerado como el
lenguaje formado por todos sus símbolos) corresponde al uni-
verso del alfabeto excluyendo la palabra vacía (potencia O de un
alfabeto);
~+ = W(~) - {A}
• Iteración, cierre o clausura:
El cierre de un lenguaje L se forma por la unión de la palabra
vacía a la clausura positiva del lenguaje;
00
L* =L+U {A}=UL i
i=O
~* = W(~)
Ejemplo: Si Ll (~2) = {O, 1},
entonces Ll (~2)* = {A, 0, 1, 00, 01 , 10, 11, 000, 001 , ... }
• Reflexión: la reflexión de un lenguaje L está formada por la aplica-
ción de la reflexión a cada una de las palabras del lenguaje;
Ejemplo: Si L2(~2 ) = {O, 1, 00, lO} , entonces
L2(~2) - 1 = {O, 1, 00, 01}
2.1.4 Otras definiciones
• Producción o regla, (x ::= y): es un par ordenado de palabras
(x, y) , x, y E ~*. Tiene elsignificado, que se matizará posteriormente,
de que si se encuentra x como parte de cualquier palabra v, se puede
sustituir x por y en v, lo que permite transformar palabras en otras.
,
12 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F OruLUES
Ejemplo: En E2 , se podrían tener las producciones
(000 ::= 010) ó (10 ::= 01)
• Derivación directa, v -+ w: aplicación de una producción
(x ::= y) a una palabra v para convertirla en otra palabra tL' donde
v = z . x . u, w = z . y. u (v, w, z, u E E*).
Se cumple que, para cada producción (x ::= y), existe una derivación
directa de x a y : x -+ y, lo que se deduce de lo anterior, sin más que
hacer z = u = A.
Ejemplo: Con las producciones PI = (000 ::= 010) y
P2 = (10 ::= 01), y la palabra 1000, se pueden hacer la.s
siguientes derivaciones directas:
1000 ~ 1010, 1010 ~ 0110, 0110 ~ 0101, Y
0101 ~ 0011
• Derivación, v -+* w: aplicación de una secuencia de produccion a
una palabra.
Ejemplo: En el ejemplo anterior, la ejecución continuada
de las derivaciones directas, proporciona una derivación de
la palabra 1000 a la palabra 0011:
1000 ~ 1010 ~ 0110 ~ 0101 ~ 0011
Otra posible derivación sería pasar de la palabra 1000 a la
palabra 0110.
• Derivación más a la izquierda: si se utiliza en cada derivación
directa la producción aplicada a los símbolos más a la izquierda de la
palabra.
Ejemplo: En el ejemplo anterior de derivación, la derivación
más a la izquierda sería:
1000 ~ 0100 ~ 0010 ~ 0001 ~ 0101 ~ 0011
'.
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 13
• Derivación más a la derecha: si se utiliza en cada derivación
directa la producción aplicada a los símbolos más a la derecha de la
palabra.
Ejemplo: En el ejemplo anterior de derivación, la derivación
más a la derecha sería:
1000 ~ 1010 !4 1001 !4 0101 !4 0011
2.2 Gramáticas formales
Las gramáticas formales son descripciones estructurales de las sentencias de
los lenguajes, tanto formales (lenguajes de programación), como naturales
(humanos). Las definiciones proporcionadas en la sección anterior de los
lenguajes son extensionales; es decir, para describir el lenguaje se enumeran
todas las palabras que lo forman. Las gramáticas permiten describir de
forma intensional a los lenguajes; se describirán los lenguajes mediante: el
alfabeto sobre el que se construirán sus palabras; un símbolo inicial del que
partirá la obtención de cualquiera de las palabras del lenguaje, denominado
axioma; un conjunto de símbolos especiales denominados no terminales que
permiten representar subconjuntos del lenguaje o estados intermedios de la
generación de las palabras del lenguaje; y un conjunto de producciones, que
permitirán realizar las transformaciones desde los símbolos no terminales a
las palabras del lenguaje. Por lo anterior, pese a que normalmente se dice
que una gramática genera un lenguaje, en este libro también se dirá que
una gramática describe un lenguaje.
2.2.1 Definiciones
• Gramática formal, G: se define como una cuádrupla
donde
- ~T es el alfabeto de los denominados símbolos terminales
l ,
/" .....
14 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F ORMALES
- L,N es el alfabeto de los denominados símbolos no terminales.
cumpliéndose:
y
L,T n L,N = 0
8 es un símbolo no terminal especial (8 E L,N), denominado el
axioma de la gramática
- P es un conjunto finito de reglas (o producciones) que tienen
como única restricción que en la parte izquierda de las produc-
ciones debe haber al menos un símbolo no terminal. Es decir.
P = {(u ::= v)lu = xAy,u E L,+,v,x,y E L,*,A E L,N}
Ejemplo:
G l = ({O,l},{A,B},A,P)
donde
P = {(A ::= lBl), (A ::= OBO), (B ::= A), (B ::= 1),
(B ::= O), (B ::= A)}
Una simplificación usual al describir las reglas de una gramá.tica es
agrupar todas las producciones de cada símbolo no terminal y separar
las partes derechas por el símbolo l.
Ejemplo: Las producciones del ejemplo anterior se podrían
describir como:
A ::= lBl lOBO
B ::= A 11 1 O 1 A
• Forma sentencial: x es forma sentencial si existe una derivación
desde el axioma hasta esa palabra; es decir, 8 -+* x
Ejemplo: Dada la gramática definida anteriormente, G l.
las siguientes son formas sentenciales:
- 010: A -+ OBO -+ 010
,
-,
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 15
lAl: A -+ lBl -+ lAl
1001: A -+ lBl -+ lAl -+ lOBOl -+ 1001
• Sentencia: x es sentencia si es forma sentencial y todos sus símbolos
pertenecen al alfabeto de símbolos terminales; es decir, S -+* x, y
x E L:Y.
Ejemplo: En el ejemplo anterior, 010 y 1001 son sentencias,
mientras que lAl no lo es.
• Lenguaje generado por una gramática, L(G): es el conjunto
de todas las sentencias de la gramática; es decir, todas las palabras
que se pueden obtener a partir del axioma de la gramática por la
aplicación de derivaciones:
L(G) = {xlS -+* x,x E L:y}
Ejemplo: El lenguaje generado por la gramática G1 sería:
Lal = {11,101, 111,00,000,010, 1001, 1111,0000,0110, ... }
Como se puede observar, el lenguaje obtenido es el de las
palabras binarias simétricas o palíndromas
(L = {xix = x- 1 }).
• Equivalencia de gramáticas: dos gramáticas G1 y G2 son equi-
valentes, denotado G1EG2, si L(G¡) = L(G2 ); es decir, si generan el
mismo lenguaje.
Ejemplo: Dada la G1 definida anteriormente y la G2 defi-
nida como:
G2 = ({O , l} , {A , B ,C, D} , A ,P)
donde
......
16 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F ORMALES
P = {(A ::= 1B1), (A ::= OCO), (B ::= D ), (D ::= A ).
(D ::= 1) , (D ::= O), (D ::= A) , (C ::= D )}
G I y G2 son equivalentes ya que L(G¡) = L (G2 ).
• Regla compresora: aquélla cuya parte derecha está formada por
menos símbolos que la parte izquierda (al ::= a 2, la21 < 101). en
ejemplo de este tipo de reglas son las reglas en las que la palabra nl.CÍa
es la parte derecha de la regla: x ::= A. Se denominan así porque
transforman una palabra en otra de menor longitud.
Ejemplo: oeo ::= 1 y A ::= A son reglas compresoras.
2.2.2 Tipos de Gramáticas
Noah Chomsky definió cuatro tipos de gramáticas formales , que se dife-
rencian en los tipos de producciones de la gramática. Esta clasificación
describe las gramáticas desde los tipos más generales a los más específicos.
dependiendo de la forma de las reglas de la gramática. Esta clasificación
permite introducir, al mismo tiempo, una clasificación en los lenguajes que
las gramáticas generan, y, también, una clasificación en los autómatas que
reconocen los lenguajes generados por las gramáticas .
• Tipo O (sin restricciones): en la parte izquierda tiene que haber
al menos un símbolo no terminal. Respecto a las partes derechas de
sus producciones no hay ningún tipo de restricción;
P = {u ::= vlu = xAy,u E 1:;+,v, x, y E 1:;*, A E 1:;N}
Ejemplo: Una posible gramática de tipo O sería la siguiente:
G3 = ({O , l} , {A,B ,S} , S,P)
donde
P = {(S ::= AO), (AO ::= 1B1), (lA ::= OBO), (B ::= A),
(B ::= 1), (B ::= O)}
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO . 17
El lenguaje generado por esta gramática es:
LC3 = {11,lOl,11l}
• Tipo 1 (dependientes del contexto o sensibles al contexto):
las partes izquierdas y derecha tienen que tener una parte común y
sólo se admite como regla compresora la regla S ::= >..
P = {(S ::= >') ó (x Ay ::= xvy)lx,y E I:*,A E I:N,v E I:+}
Se denominan dependientes del contexto porque se tiene en cuenta
lo que viene antes y después del símbolo que se sustituye. Así, en
la fórmula anterior, x e y son el contexto de la transformación de
A en v. La peculiaridad de estas gramáticas consiste en que las de-
rivaciones producidas por aplicación de sus reglas cumplen que las
palabras siempre tienen longitud mayor o igual que las anteriores en
la derivación.
Ejemplo: La gramática G3 no es de tipo 1, ya que hay
una regla compresora cuya parte izquierda no es el axioma
(B ::= >.). Una gramática de tipo 1 sería la siguiente:
G4 = ({O,l},{A,B},A,P)
donde
P = {{(A ::= lBl), (A ::= 11), (lBl::= 101), (lBl ::= 11l)}.
Esta gramática es equivalente a la anterior, ya que generan
el mismo lenguaje:
LC4 = LC3 = {11, 101, l11}
.......
18 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F ORM ALES
• Tipo 2 (independientes del contexto): en estas gramát icas. la
parte izquierda de las producciones sólo puede tener un símbolo no
terminal:
p = {(S ::= >') ó (A ::= v)IA E ~N,V E ~+}
Estas gramáticas se denominan de contexto libre, porque a la hora
de transformar una palabra en otra, el símbolo no terminal que se
transforma no depende de los que estén a la izquierda o derecha. Así.
cuando se realicen derivaciones en las que se transforme el símbolo .--1
de la fórmula anterior, no hace falta saber qué hay alrededor de él.
Ejemplo: La gramática G4 no es de tipo 2, ya que varias
reglas tienen en la parte izquierda más de un símbolo no
terminal. Un ejemplo de gramática de tipo 2 equivalente a
las anteriores sería la siguiente:
G5 = ({O,l},{A,B},A,P)
donde
P = {(A ::= 1B1), (A ::= 11), (B ::= 1), (B ::= O)}.
Esta gramática es equivalente a la anterior, ya que generan
el mismo lenguaje:
LC5 = LC4 = {11, 101, 111}
• Tipo 3 (regulares o lineales)
Estas gramáticas, las más restrictivas, pueden ser de dos tipos:
Lineales por la izquierda:
P = {(S ::= >') ó (A ::= Ba) ó (A ::= a)IA, B E ~N , a E Er}
Lineales por la derecha:
P = {(S ::= >') ó (A ::= aB) ó (A ::= a)IA,B E ~N , a E Er}
=
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 19
Ejemplo: La gramática Gs no es de tipo 3, ya que las dos
primeras reglas tienen partes derechas que no se ajustan a
ninguna de las dos categorías de gramáticas regulares. Un
ejemplo de gramática de tipo 3 lineal derecha equivalente
a las anteriores sería la siguiente:
G6 = ({O,l},{A,B},A,P)
donde
P = {(A ::= lB), (B ::= 1), (B ::= OC) , (B ::= lC), (C ::= l)}.
Esta gramática es equivalente a la anterior, ya que generan
el mismo lenguaje:
LG6 = LG5 = {11, 101, l1l}
• Existe, además, una jerarquía entre los tipos de gramáticas tal que
las gramáticas del tipo i son más generales que las de tipo i + 1.
Formalmente, G3 ~ G2 ~ GI ~ Go
2.2.3 Árboles de derivación
Son una forma de representar las derivaciones, siendo utilizados, por ejem-
plo, en la construcción de compiladores para representar el análisis sintáctico
de los programas fuente y sirviendo de base para la generación de código.
Sólo se pueden definir árboles de derivación para gramáticas de tipo 1 o
más restrictivas (tipos 2 y 3). En los árboles de derivación:
• el axioma se representa en la raíz del árbol;
• los nodos hojas del árbol son símbolos terminales de la gramática;
• los nodos intermedios son símbolos no terminales de la gramática; y
• las derivaciones se representan creando tantos sucesores del símbolo
no terminal de la izquierda de las producciones como símbolos (ter-
minales y no terminales) aparezcan en la parte derecha de las pro-
ducciones.
20 CAPÍTULO 2. LENGUAJES y G RAc\1ÁTICAS F OruLU ES
Ejemplo: Supóngase la siguiente gramática:
G7 = ({O,l,[,J,+,*},{E},E,P)
P = {(E ::= [EE+]), (E ::= [EE*]), (E ::= O) , (E ::= In
La figura 2.1 muestra un posible árbol de derivación para ob e-
ner la palabra [O[OhJ+]).
E
E E +
I
O E E *
I
O 1
Figura 2.1: Ejemplo de árbol de derivación de la palabra [0[01 *J+J.
2.2.4 Ambigüedad
El concepto de ambigüedad en la teoría de lenguajes y gramáticas es similar
al empleado en el lenguaje coloquial; existe más de una forma de generar
una palabra a partir del axioma de una gramática. La ambigüedad puede
surgir a varios niveles: en sentencias, lenguajes, y gramáticas. A la hora
de utilizar eficientemente los lenguajes y gramáticas, es conveniente que no
exista ambigüedad, pues provoca que el análisis de las sentencias no sea
determinista .
• Sentencia: una sentencia es ambigua si tiene más de una derivación
o árbol de derivación.
Ejemplo: En el caso de la gramática
Gs = ({l} , {A,B} ,A, {(A ::= 1B) , (A ::= l1) , (B ::= 1)} )
la sentencia 11 puede ser obtenida por las dos derivaciones
siguientes: A -+ lB -+ 11 Y A -+ 11.
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 21
• Gramática: una gramática es ambigua si tiene al menos una sen-
tencia ambigua.
Ejemplo: La gramática Gs es ambigua, ya que 11 es una
sentencia y es ambigua.
• Lenguaje:
un lenguaje es ambiguo si existe una gramática ambigua que lo
genera.
Ejemplo: El lenguaje Ls = {11} es ambiguo ya que la
gramática G 8 lo genera y es ambigua.
si todas las gramáticas que generan un lenguaje son ambiguas,
el lenguaje es inherentemente ambiguo.
Ejemplo: El lenguaje Ls no es inherentemente ambiguo
ya que la siguiente gramática lo genera y no es ambigua.
G9 = ({l},{A},A,{(A ::= 11)})
2.2.5 Recursividad
El concepto de recursividad en lenguajes y gramáticas también es análogo
al utilizado en otras ramas de la computación; la definición de un concepto
utiliza a ese mismo concepto en la definición. Existen varios niveles de
recursividad:
• Producción recursiva: si el mismo símbolo no terminal aparece en
los dos lados de la producción; es decir, existe un A E ¿'N tal que
(A ::= xAy) E P , (x , y E ¿,*)
Ejemplo: Las siguientes producciones son recursivas:
A ::= OAO, B ::= BlO, C ::= 111C
J.
/
22 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS Fo~ L~LES
• Gramática recursiva: si existe al menos una producción recursiva
en su conjunto de producciones.
• Recursividad por la izquierda: si el símbolo no terrrúnal aparece
el primero de la parte derecha; es decir , A ::= Ay. (A E ~ _ -.y E ~' ) .
Ejemplo: En el ejemplo anterior, B ::= BlO es recursi -a
por la izquierda.
• Recursividad por la derecha: si el símbolo no terminal aparece el
último en la parte de la derecha; es decir, A :: = x A , (A E E s . .r e ~') .
Ejemplo: En el ejemplo anterior, C ::= 111C es rec :I\-a
por la derecha.
• Recursividad por la izquierda en más de un paso: si ~ iene
una regla no recursiva por la izquierda A ::= B x , A f:- B . 1--1. B E
'E N, X E E*), pero desde B hay una derivación del tipo B ---' . A. y.
(y E 'E*), entonces existe recursividad por la izquierda en más de
un paso con respecto al símbolo no terminal A, ya que exis e una
derivación desde él de la siguiente forma: A -+* Ayx .
Ejemplo: En las siguientes producciones hay recursi\idad
por la izquierda en más de un paso.
E .. = T + E I T * E I variable I número
T .. = E I (E)
ya que E -+ T + E -+ E + E.
Normalmente, cuando se utilizan las gramáticas, como en el caso de la
construcción de compiladores de lenguajes de alto nivel, se necesita que las
gramáticas no sean recursivas (especialmente la recursividad por la izquier-
da). Para eliminar la recursividad se recurre al siguiente procedimiento,
dividido en dos pasos.
• Primer paso. Eliminación de recursividad por la izquierda en las
producciones de un mismo símbolo no terminal.
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 23
Para cada A E ~N
Si las producciones de A son:
p = (A ::= A· allA· a21·· ·IA· a nl,8ll,821·· ·1,8m)
donde ,8i no comienzan por A
Entonces Se crea un nuevo símbolo no terminal A';
~N = ~N U {A'};
P := (p- P) U {A ::=,81· A' I,82· A'I·· .1,8m· A' ,
A' ::= al . A'la2 . A'I·· .Ian . A'I),}
Como muchas veces no se desean las producciones del tipo
(A ::= ),) cuando A no es el axioma, otra variante equivalente del
procedimiento anterior consiste en modificar el conjunto de produc-
ciones resultante, sustituyendo el nuevo símbolo no terminal A' en
cada parte derecha de producción por )" de la siguiente forma:
P := (p- P) U {A ::=,81· A' 1,82 . A'I · · ·1,8m· A' I,8ll,821·· ·1,8m,
A' ::= al· A'la2 . A'I· · ·Ian . A' la lla21·· .Ian }
Ejemplo: Supóngase las siguientes producciones de una
gramática que genera expresiones aritméticas:
P = {(E ::= E + E), (E ::= E * E), (E ::= variable),
(E ::= número)}
Para eliminar la recursividad por la izquierda de las dos pri-
meras producciones, se crea un nuevosímbolo no terminal
E' , se eliminan todas las producciones en P del conjunto
de producciones de la gramática y se crean las siguientes
nuevas producciones:
p' = {(E ::= variable E'), (E ::= número E'),
(E' ::= +EE' ), (E' ::= *EE' ), (E' ::= ),)}
24 CAPÍTULO 2. LENGUAJES y GRA~ÜnC . .\S F OruLUES
o bien:
p" = {(E ::= variable E'), (E ::= número E/ ).
(E ::= variable ) , (E ::= número ) ,
(E' ::= +EE/), (E' ::= *EE/), (El :: = + E ). (E :: = %E )}
• Segundo paso. Eliminación de recursividad por la izquierda en más
de un paso.
Aún cuando se elimine la recursividad por la izquierda de las p uc-
ciones de todos los símbolos no terminales, no se asegura que haya
eliminado de todas las producciones de la gramática. ya que puede
estar oculta por producirse en más de un paso. El algori tmo para la
eliminación de la recursividad por la izquierda en más de un ras es
el siguiente:
1. Disponer los símbolos no terminales en algún orden
Al ,A2 ... An
2. For i:=1 to n
For j:=1 to n
2.1 Si i i- j, reemplazar cada producción Ai ::= A j . ') por:
Ai ::= (h .1'162 ·1'1 · . ·16k . l'
donde Aj ::= 611621 ... 16k son todas las reglas de A)
2.2 Eliminar la recursividad por la izquierda de las A ,
Ejemplo: En el ejemplo de la gramática de expresion
aritméticas, se enumerarían primero los símbolos no termi-
nales, como, por ejemplo, Al = E, A2 = T. A continua-
ción, se realizan los bucles como sigue:
• i=1 (Al = E), j=1 (Al = E). Se reemplazarían las
producciones E ::= Ea por las que se obtendrían de
sustituir la E de la parte derecha por todas las pro-
ducciones a las que lleva E. Como no hay ninguna
producción de ese tipo, no se hace nada. El paso 2.1
del algoritmo eliminaría la posible recursión izquierda
en Al = E. Como no hay, se sigue con la siguiente
iteración del bucle interno.
L ENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 25
• i=l (Al = E), j=2 (A2 = T). Se reemplazan todas
las producciones E ::= Ta. Esto daría lugar al nuevo
conjunto de producciones:
E .. = E + E I E * E I (E) + E I (E) * E I
variable I número
T .. = E I (E)
y se elimina la recursión en E , quedando:
E ··=
E'··=
T··=
(E) + EE' I (E) * EE' I variable E' I
número E'
+EE' I *EE' 1).
E I (E)
• i=2 (A2 = T) , j=l (Al = E) . Se reemplazan las pro-
ducciones T ::= Ea, dando lugar a:
E ··=
E'··=
T· ·=
(E) + EE' I (E) * EE' I variable E' I
número E'
+EE' I *EE' I ).
(E) + EE' I (E) * EE' I variable E' I
número E' I (E)
y se eliminaría la recursión en T si la hubiera.
• i=2 (A2 = T) , j=2 (A2 = T). Se reemplazan las pro-
ducciones T ::= Ta. Como no hay ese tipo de pro-
ducciones, no se producen cambios y el conjunto de
producciones en el que se ha eliminado la recursión es:
E··=
E'··=
T··=
(E) + EE' I (E) * EE' I variable E' I
número E'
+EE' I *EE' I ).
(E) + EE' I (E) * EE' I variable E' I
número E' I (E)
2.2.6 Factorización a izquierdas
Otro problema común cuando se diseña una gramática es el hecho de que
aparezcan producciones de un mismo símbolo no terminal en cuya parte de-
recha, la primera parte sea común. Por ejemplo, las siguientes producciones
26 CAPÍTULO 2. LENGUAJES y GRAMÁT ICAS FOR~L-\LES
pueden estar tomadas de una gramática de un lenguaje de programación
de alto nivel.
s .. = If e Then S Else S I If e Then S I
Repeat S U ntil e I Repeat S Forever
donde ~T = {If,Then,Else,Repeat ,Until,Forever} y ~N = {S. e } .
Este problema presenta dificultades a la realización de compiladores
para un lenguaje definido con esa gramática. El proceso que elimina ese
problema se denomina factorización a izquierdas, cuyo algoritmo se detalla
a continuación:
Por cada A E ~N
Si A ::= (3. all(3· a2
Entonces cambiar esas producciones por:
A ::= (3. A'
A' ::= alla2
Ejemplo: En el ejemplo anterior, la aplicación de la factorización
a izquierdas crearía dos nuevos símbolos no terminales, A' y S' .
y generaría las siguientes producciones.
S"=
A'··=
S" '=
If e Then S A' I Repeat S S'
Else S I ,\
U ntil e I Forever
LENGUAJES , GRAMÁTICAS y A UTÓMATAS: UN ENFOQUE PRÁCTICO 27
EJERCICIOS
Ejercicio 12.11
Dados los siguientes alfabetos:
• ~¡ = {1 , 2, 3,4, 5, 6,7,8} Y
• ~2 = {a,b,c,d, e,j,g,h}
y los lenguajes:
• L¡(~¡) = {xi x E ~l} Y
• L2(~2) = {xi x E ~2},
Definir los lenguajes Ll U L2, L l . L2 Y (L 1 . L2)2.
{xix E ~l ó x E ~2} =
{1,2,3,4 , 5,6, 7,8 ,a, b,c,d,e, j , g, h}
{xylx E ~l e Y E ~2} =
{la, 2a , . .. , 8a , lb, ... , 8b, ... , lh, ... , 8h} .
En este caso, una numeración muy utilizada para los tableros
de ajedrez es numerar las filas del 1 al 8 y las columnas de
la a a la h, con lo que el lenguaje resultante de Ll . L2
representaría todas las casillas del ajedrez .
• (L 1 • L2)2 = {x2 = X • xix E (L¡ . L2)} =
= {lala , . .. , la8a , lalb, . .. , la8b, . .. , lbla , . . . , 8h8h}.
El número de palabras del lenguaje resultante sería I(L¡ . L2)21 = 84 .
c1
28 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS F OrulALES
Ejercicio 12.21
Supóngase que la Dirección General de Tráfico desea construir u sistema
que sea capaz de determinar si una secuencia de símbolos forma una ma rícula
española válida. Se pide diseñar el lenguaje que serviría de base para dicho
sistema.
Se va a construir el lenguaje final en función de lenguajes más senc i-
llos. Así, primero se definirá el lenguaje de los símbolos que representan a
las provincias españolas: Lp = {A, AB, AL, ... , ZA}. Luego se define el
lenguaje formado por los dígitos:
LD = {a, 1, 2, 3, 4, 5, 6,7,8, 9}
Otro lenguaje será el formado por las letras del alfabeto, exceptuando
la Ñ, Q, R y las letras compuestas: LL = {A, B, C, ... , Z}. Como último
lenguaje simple, se partirá del lenguaje formado por el guión: Le = { - } .
A partir de estos lenguajes simples, se pueden ir realizando operaóones
sobre lenguajes para formar el lenguaje final. Así, las matrículas antiguas,
como, por ejemplo, M - 624945, se pueden definir como:
Las matrículas nuevas, como, por ejemplo, TE - 4123 - A ó
SG - 2334 - LG se pueden definir como:
Habría que hacer una salvedad con algunas matrículas no permit idas,
como, por ejemplo, las que tienen una combinación de dos letras finales con
una A como letra final (BA , CA, .. . ). Si se denomina Lp al lenguaje for-
mado por las combinaciones de dos letras no permitidas en las matrículas,
el lenguaje que describe a las matrículas sería:
LENGUAJ ES, G RAMÁTICAS y A UTÓ MATAS : UN E NFOQUE PRÁCTICO 29
Ejercicio 12.31
Supóngase que el Ministerio de Economía y Hacienda ha decidido aceptar
las declaraciones de la renta interactivamente por Web. Para ello, el usuario
de be rellenar los datos relativos a la declaración utilizando un interface que
debe detectar errores en la entrada de datos. ¿Qué lenguajes describen los
siguientes campos?
1. Los nombres y apellidos pueden ocupar un maxlmo de 40 caracteres,
que podrán ser letras o guiones y pueden estar separados por blancos
(nombres compuestos) .
2. La casilla correspondiente al DNI,l puede rellenarse con el DNI o con el
NIF. El DNI es una secuencia de, como máximo, ocho dígitos y el NIF
se forma con el DNI seguido de una letra.
3. La dirección postal debe estar precedida de el si es una calle, Pza. si
es una plaza, Avda. si es una avenida , o R. (resto) si no es ninguna de
estas tres cosas, pudiendo aparecer en minúsculas o mayúsculas. A conti-
nuación debe estar el nombre de la calle , que debe ocupar un máximo de
50 caracteres en los que sólo pueden aparecer letras, espacios en blanco,
o gUiones.
4. El número de la dirección postal debe ser una secuencia de, como máximo,
cuatro dígitos.
5. El código postal está compuesto de cinco dígitos.
Se definen los siguientes alfabetos básicos y los lenguajes formados sólo
por los símbolos de los alfabetos:
• L:D = {a, 1,2,3,4,5,6, 7,8, 9} = L D
• L:L = {a, b,c, ... , z, A, B ,C, ... , Z}=LL
1 Documento N aciona! de Identidad
..... - ,...,
30 CAPÍTULO 2. LENGUAJESy GRAMÁTICAS FO~~ALES
• L;e = { - } = Le
• L;s = {/} = Ls
• L;p={.}=Lp
donde # representa al espacio en blanco. A partir de estos lenruajes,
se van a formar los lenguajes pedidos:
1. LN = [LL U LB U Le]40
Si se quisiera evitar que aparecieran determinadas combinaciones no
deseadas, como, por ejemplo, dos guiones seguidos o un guión seguido
de un blanco, habría que cambiar la unión de los lenguajes por otra
fórmula más específica. Por ejemplo, si se quieren evitar dos guiones
seguidos, se podría poner:
L N= (LL U LB)40 U [(LLLLLL U LLLLLB U LLLLLe U LLLBLLU
ULLLBLB U LLLBLe U LLLeLL U LLLe LBU
ULBLLLL U LBLLLB U LBLLLe U LBLBLL U
ULBLBLB U LBLBLe U LBLeLL U LBLCLB)13.
·(LL U LB)] =
= (LL U LB)40 U [((LL U LB)3 U (LL U LB)Le(LL U LB )U
U(LL U L B)2 Le)13 . (LL U LB)]
Si se hace (LL U LB) = LLB, se tendría:
Lo que se ha hecho es enumerar las posibles combinaciones de los
lenguajes LL , LB Y Le, que son los que pueden aparecer. evitando
aquellas combinaciones en las que haya dos guiones juntos. Para
ello, también hay que evitar que puedan aparecer al final de una
combinación y al principio de otra, ya que, como se repiten 13 \'eces
estas combinaciones de tres elementos (13 x 3 + 1 = 40). podrían
aparecer dos guiones juntos de dos pasos consecutivos.
8 .
2. LDNI=[Ui=lLb]·(LLU{A})
Es decir, son todos los posibles números entre O y 99999999 seguidos .
o no, de una letra.
.i
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 31
3. Como en el caso de la dirección, se marca cuáles serán los comienzos
de los códigos ("el", "Pza.", "Avda." o "R."), el lenguaje se podría
formar uniendo esos prefijos a un conjunto de letras, blancos y guiones
cuya cardinalidad será 50 menos lo que ocupen cada uno de esos
prefijos. Podría ser:
LDP =[( {e} U {e}) . Ls' (LL U LB U LC)48]U
[({p} U {P})· ({z} U {Z})· ({a} U {A})· Lp'
(LL U LB U LC)46]U
[({a} U {A})· ({v} U {V})· ({d} U {D})· ({a} U {A})· Lp'
(LL U LB U LC)45]U
[({r} U {R})· Lp' (LL U LB U LC)48]
4. En el caso del número de la dirección, puede ser cualquier número
entre O y 9999:
5. Por último, el código postal estaría formado por cinco dígitos obliga-
toriamente, pudiendo definirse como:
Realmente, habría que comprobar que el código postal es uno de los
válidos. Para ello se podrían enumerar todos los elementos válidos
del lenguaje Lc p y formar con esos un nuevo lenguaje Lc pv.
En los siguientes capítulos se estudiarán los autómatas, que son sistemas
que permiten, dado un lenguaje y una palabra, decidir si la palabra perte-
nece o no al lenguaje. Esto permitiría, fácilmente , construir un autómata
para cada uno de estos lenguajes y que se encargara de la labor de com-
probación de que se han introducido los datos correctamente.
32 CAPÍTULO 2. LENGUAJES y GRA~L\nCAS F ORliU-ES
Ejercicio 12.41
Obtener derivaciones de las palabras 002 y 0001 a partir de la . iente
gramática:
G = ({O, 1, 2} , {A , B}, A, {(A ::= OE) , (A ::= 2) , (E ::= OA ). (B ::= )})
Describir el árbol de derivación y obtener el lenguaje que ge era .
Las palabras se pueden obtener por las siguientes derivacion
• 002: A --t OE --t OOA --t 002
• 0001: A --t OB --t OOA --t OOOE --t 0001
Los árboles de derivación aparecen la figura adjunta.
A
A
0)\
° A
I
2
°
A
A
°A
° B I
Para obtener el lenguaje, habrá que analizar qué palabras pueden deri-
varse desde el axioma. ASÍ, se pueden obtener las siguientes derivaciones:
.A--t2
• A --t OB --t 01
• A --t OB --t OOA --t 002
• A --t OE --t OOA --t OOOB --t 0001
• A --t OE --t OOA --t OOOE --t OOOOA --t 00002
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 33
Por tanto, puede aparecer un 2 precedido de un número par de Os ó un
1 precedido de un número impar de ls. Si se define un lenguaje Ll como:
y un lenguaje L2 como:
Entonces, el lenguaje generado por la gramática se puede definir como
Le = Ll U L 2 , o, lo que es lo mismo:
Ejercicio 12.51
Dada la siguiente gramática, realizar factorización a izquierdas y eliminación
de recursividad por la izquierda .
G = ({ or,and,not,=,(.),id} , {C} , C, P)
donde
P = {(C::= C and C),
(C::= C or C),
(C::= not C),
(C::= ( C = C )),
(C::= id)}
Para factorizar a izquierdas se reemplazan las dos primeras producciones
por:
G::=CG'
G'::= or G I and C
A continuación, se elimina la recursividad por la izquierda de la produc-
ción (C :: =C C') creando un nuevo símbolo no terminal Gil y cambiando el
conjunto de producciones P por:
...
34 CAPÍTULO 20 LENGUAJES y GRA. L.\T1CA5 F Oru L-\ LES
e::= not e e" I ( e = e ) e" I id e"
e'::= or e I and e
e"::= e' e" I .\
Ejercicio 12.61
Dada la siguiente gramática, que utiliza la notación polaca i ersa ( odos
los operandos de las operaciones se colocan antes de los operadores), aa m ar
a izquierdas y eliminar la recursividad por la izquierdao
G = ({id, num, fune , +, *, j, - , (,), o,;, <, >, =} , {S, N , M , 0 0 R }o o P )
donde
P = {(S ::= S; S), (S :: = So), (S ::= (NNR)), (S ::= (idN = )) 0
(N ::= M NON), (N ::= M NO), (N ::= id), (N ::= num)o
(M ::= N), (M ::= fune(N)) , (M ::= fune(M)) ,
(O ::= +), (O ::= *), (O ::= -), (O ::= j),
(R ::=<), (R ::=», (R ::==)}
Mostrar dos sentencias del lenguaje generado por la gramática .
La factorización a izquierdas influye en las producciones:
(S ::= S; S) , (S ::= So), (S ::= (NNR)), (S ::= (idN =)) ,
(N ::= MNON), (N ::= MNO) , (M ::= fune(N)) , (M :: = func (.U ))
Aplicando el algoritmo, quedarían como:
(S 00- SS') (S' 00 _ 0 S) (S' 00- ) .. - , .. - , , .. -.,
(S ::= (S") , (S" ::= NNR)) , (S" ::= idN =)) ,
(N ::= MNON' ), (N' ::= N), (N' ::= .\),
(M ::= fune(M/), (M' ::= N)), (M' ::= M))
La gramática modificada, quedaría:
G' = (~~, ~~, S, PI)
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 35
donde
E!z, = ET = {id, num, fune, +, *, /, -, (,),.,; ,<, >, =}
E~ = {S,S',S",N,N',M,M',O,R}
p' = {(S ::= SS'), (S ::= (S"),
(S' .. -. S) (S' .. - ) .. -, , .. -.,
(S" ::= NNR)), (S" ::= idN =)),
(N ::= M NON') , (N ::= id), (N ::= num),
(N' ::= N), (N' ::= .\),
(M ::= N), (M ::= fune(M'),
(M' ::= N)), (M' ::= M))}
(O ::= +),(0 ::= *),(0 ::= -),(0 ::= /),
(R ::=<), (R ::=», (R ::==)}
La recursividad por la izquierda aparece en las producciones correspon-
dientes a 5, N Y M. Estas dos últimas en más de un paso. Para eliminar
la recursividad por la izquierda en más de un paso, se recurre al algoritmo,
ordenando los símbolos no terminales por el mismo orden en que aparecen
en el conjunto E~, por ejemplo; Al = S, A2 = S', ... , Ag = R. Luego,
se realizan bucles en los que se reemplazan las primeras apariciones de los
símbolos no terminales en las partes derechas de las producciones por las
partes derechas de las producciones de esos símbolos no terminales y se
elimina la recursividad por la izquierda.
• i = 1, j = 1 (S, S). Como i = j, no se hace nada en el primer paso, y
luego se elimina la recursividad por la izquierda de las producciones
de S, generando un nuevo símbolo no terminal S"I , quedando sus
producciones como:
(S ::= (S" SIII) , (SIII ::= S' SIII) , (SIII ::= .\)
• i = 1,j = 2 (S, S'). No hay producciones del tipo S ::= S' y ya se ha
eliminado la recursividad por la izquierda de S, con lo que no se hace
nada en este punto.
• Lo mismo pasa con i = 1 y j = 3 .. 9, i = 2 Y j = 1..9, e z 3,Y
j = 1..3.
• i = 3, j = 4 (S", N). En este caso, se sustituye la primera aparición
del símbolo no terminal N en la producción (S" :: = N N R)) por to-
das sus producciones, transformando dicha producción en el siguiente
conjunto:
.-
36 CAPÍTULO 2. LENGUAJES y GRA {ÁnCAS f OR.).H L ES
(S" ::= MNON'NR)), (S" ::= idNR)) , (S" :: = n -R
Como no hay recursividad por la izquierda en las prod e S" ,
se termina este paso.
• Para i = 3 y j = 5 no hay cambios, pero sí en el i = 3. = 6
(S", M) debido a los cambios producidos en S" en el pas enor.
Es necesario cambiar la M que aparece como primer '
partederecha de la producción (S" ::= MNON'NR )) por ~ partes
derechas de sus producciones. Quedarían las nuevas produccion ~ de
S" como:
(S" ::= NNON'NR)), (S" ::= func(M'NON'NR ))
que se unirían a las anteriores producciones suyas. Como no hay
recursividad por la izquierda, no hay más cambios.
• Para i = 3 y j = 7 .. 9 no hay cambios, así como para i = 4 Y j = 1..5.
• i = 4,j = 6 (N, M). Se sustituye la M de la producción
(N ::= M NON') por sus producciones , quedando:
(N ::= N NON') , (N ::= func(M' NON')
A continuación, se elimina la recursividad por la izquierda de _V .
quedando sus producciones:
(N ::= func(M' NON' N"), (N ::= idN") , (N ::= numN" ).
(N" ::= NON' N"), (N" ::= >..)
• Para i = 4, j = 7 .. 9 e i = 5, j = 1..3 no hay cambios.
• i = 5,j = 4 (N', N). Se realizan los mismos pasos anteriores . que-
dando las producciones de N' como:
(N' ::= func(M'NON'N") , (N' ::= idN") , (N' ::= numN" ). (_ ' ::= >..)
• En los siguientes pasos, no hay más cambios hasta i = 6. j = 4
(M, N) , donde se sustituye la N en la producción (M ::= ) por
sus producciones, quedando las producciones de M como:
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 37
(M ::= func(M' NON' N"), (M ::= idN") , (M ::= numN"),
(M ::= func(M')
Como no hay recursividad por la izquierda, se termina al paso, no
habiendo más cambios hasta i = 7,j = 4 (M', N), donde se sustituye
la N en la producción (M' ::= N)) por sus producciones, quedando
las producciones de M' como:
(M' ::= fune(M' NON'N")), (M' ::= idN")), (M' ::= numN")) ,
(M' ::= M))
No hay recursividad por la izquierda, con lo que se siguen los pasos
hasta i = 7,j = 6 .
• i = 7, j = 6 (M' , M). Se sustituye la producción (M' ::= M)) por:
(M' ::= fune(M' NON' N")), (M' ::= idN")) , (M' ::= numN")) ,
(M' ::= fune(M'))
que no tiene recursividad.
Como ya no hay ningún problema de recursividad, se terminaría el
algoritmo de eliminación de la recursividad por la izquierda, quedando la
siguiente gramática:
G" = (E" E" S P") T' N' ,
donde
E!f = ~~ = {id, num, fune , +, *, /, -, (,),., ; , <, >, =}
E" = {S S' S" S'" N N' N" M M' O R}
N """""
P' = {(S ::= (S"S"'),
(S' .. _. S) (S' .. - ) .. - , , .. -. ,
(S" ::= NNON'NR)) , (S" ::= fune(M'NON'NR)) ,
(S" ::= idNR)) , (S" ::= numNR)) , (S" ::= idN =)) ,
(S'" ::= S' S"') , (S'" ::= ,\)
(N ::= fune(M' NON' N"), (N ::= idN") , (N ::= numN") ,
(N' ::= fune(M'NON'N"), (N' ::= idN") , (N' ::= numN") ,
(N' ::= ,\),
I -
38 CAPÍTULO 2. LENGUAJES y GRAMÁTICAS FORMALES
(N" ::= NON' N"), (N" ::= A)
(M ::= func(M' NON' N") , (M ::= idN") , (M :: = numN" ).
(M ::= func(M')
(M' ::= func(M' NON' N")) , (M' ::= idN")) ,
(M' ::= numN")) , (M' ::= func(M'))
(O ::= +) , (O ::= *), (O ::= -) , (O ::= j) ,
(R ::=<), (R ::=», (R ::==)}
Para obtener sentencias del lenguaje, no hay más que derivar desde
el axioma, utilizando las producciones de la gramática. Si se utiliza la
gramática primitiva (sería equivalente hacerlo con la nueva), y deriyando
por la izquierda, se podrían obtener, por ejemplo, las siguientes dos sen-
tencias:
.S -+
-+
-+
-+
-+
• S -+
S; S -+ (NNR) ; S -+ (id NR); S -+ (id MNOR) ; S-+
(id NNOR); S -+ (id num NOR); S -+ (id num num OR ): S -+
(id num num * R); S -+ (id num num * < ); S -+
(id num num * < ); S. -+ (id num num * < ); (id N = ). -+
(id num num * <); (id id =).
S . -+ (NNR). -+ (num NR). -+ (num num R). -+ (num num = ) .
Ejercicio 12.71
Dada la gramática G = {~T,~N,E,P}, donde ~T
~N = {E , T , F}, E es el axioma y Pes:
E
T
F
E+ T I (E) I a
T*FI (E) I a
(E) I a
{a . - . x. ) . 0,
Eliminar la recursividad por la izquierda y construir el árbol de de rivació n
para las sentencias: a+a+a+a+a ya+(a+a).
Se eliminará primero la recursividad por la izquierda de la producción
E::= E+T. Para ello, se añadirá un nuevo símbolo no terminal A y se
sustituirá la producción por las siguientes producciones.
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 39
E .. -
A 00-
aA I a I (E)A I (E)
+TA I +T
El nuevo conjunto de producciones es:
E 00- aA I a I (E)A I (E) 00
A 00- +TA I +T 00
T 00 - T *F I (E) l a 00
F 00- (E) I a 00
Se eliminirá ahora la recursividad por la izquierda de la producción
T : : = T * F introduciendo un nuevo símbolo no terminal B. Las nuevas
producciones son:
T
B
00-
00
00-
00
(E)B I aB I (E) I a
*FB I *F
El conjunto final de producciones es:
E 00- aA I a I (E)A I (E) 00
A 00 - +TA I +T 00
T 00- (E)B I aB I (E) I a 00
B 00- *FB I *F 00
F 00 - (E) I a 00
Las figura 2.2 muestra el árbol de derivación de la primera sentencia y
la figura 2.3 el á.rbol de derivación de la segunda.
-
40 CAPÍTULO 2. LENGUAJES y GRA~L~TIC.\.S f OIDL\LES
+ T A
1\
a + a
Figura 2.2: Arbol de derivación para la sentencia a + a + a - a - a .
+ T
( E )
/\
a A
1\
+ T
I
a
Figura 2.3: Arbol de derivación para la sentencia a + (a + a).
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 41
Ejercicio 12.81
Dados los siguientes lenguajes:
• Ll = {raíces de los verbos regulares de la primera congujación}
• L 2 = {terminaciones de presente de indicativo de la primera congujación}
• L3 = {raíces de adjetivos calificativos que admiten desinencia de género}
• L4 = {morfemas de género}
• L5 = {morfemas de número}
Definir los lenguajes de las formas verbales regulares de presente de indi-
cativo y de los adjetivos calificativos masculinos y femeninos tanto singulares
como plurales.
Simplificando estos lenguajes pueden ser:
• Ll = {cant, am, salt, ... }
• L 2 = {o, as, a, amos, ais, an }
• L3 = {bonit, ric, guap, amarill, ... }
• L4 = {o, a }
• L5 = {A, s }
Así, L 1 ·L2 define el lenguaje de las formas verbales regulares de presente
de indicativo de la primera conjugación:
Ll . L 2 = {canto, cantas, ... , ama, amamos, . .. , saltais, saltan, ... }
Para los adjetivos, L3 . L4 incluye los adjetivos masculinos y femeninos :
L3 . L4 = {bonito, bonita, amarillo, amarilla, ... }
Por último, el lenguaje L 3·L4·L5 incluye también los adjetivos singulares
y plurales, pues:
L3 . L4 . L 5= {bonito, bonita, bonitos, bonitas, amarillo, amarilla, .. . }
...
Capítulo 3
GRAMÁTICAS REGULARES y
AUTÓMATAS FINITOS
En este capítulo se van a estudiar las gramáticas regulares, de tipo 3 según
la clasificación de Chomsky. A continuación, se tratarán los autómatas
que reconocen el lenguaje generado por una gramática de ese tipo: las
Máquinas Secuenciales; los Autómatas Finitos Deterministas, No Determi-
nistas, y Probabilísticos; y los autómatas de Células de McCulloch-Pitts.
También se estudiarán las Expresiones Regulares que permiten describir de
forma concisa el lenguaje generado por una gramática de tipo 3 (Lenguajes
Regulares) y, por tanto, aceptado por un autómata de los tipos enunciados
anteriormente.
3.1 Gramáticas regulares
Las Gramáticas Regulares son el tipo más específico de gramática según la
jerarquía de Chomsky. Como se ha visto, las producciones pueden ser de
dos tipos, según sea regular (lineal) por la derecha o por la izquierda:
• Lineales por la izquierda:
p = {(S ::= A) ó (A ::= Ba) ó (A ::= a)IA, BE ¿'N, a E ¿'T}
• Lineales por la derecha:
p = {(S ::= A) ó (A ::= aB) ó (A ::= a)IA,B E ¿'N,a E ¿'T}
43
44 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FI ITOS
A continuación, se estudiará la equivalencia entre ambas representa-
ciones, ya que, para cada Gramática Lineal derecha existe una Gramática
Lineal izquierda equivalente y viceversa. El algoritmo para convertir una
gramática lineal derecha en otra equivalente lineal izquierda tiene cuatro
pasos:
1. Se transforma la gramática de forma que no haya ninguna regla en
cuya parte derecha esté el axioma de la gramática (cuando esto ocu-
rre se denomina axioma inducido) . Para ello, se aplica el si!!UÍente
proceso:
• Se crea un nuevo símbolo no terminal S'.
• Por cada regla de la forma S ::= x, donde S es el axioma.y
x E ~*, se crea una nueva regla S' ::= x.
• Cada regla de la forma A
transforma en A ::= xS'y.
2. Se crea un grafo G dirigido:
xSy (A E ~N, x, Y E L' ). se
• Para cada A E ~N U {A} se crea un nodo.
• Para cada producción (A ::= aB) E P (A, B E ~N, a E LT ). se
crea un arco etiquetado con a que va del nodo A al nodo B.
• Para cada producción (A ::= a) E P (a E ~T) , se crea un arco
etiquetado con a que va del nodo A al nodo A.
• Si existe una regla S ::= A, se crea un arco sin etiqueta de de el
nodo del axioma al nodo A.
3. Se crea otro grafo G' a partir de G:
• Se intercambian las etiquetas del axioma, S, y A.
• Se invierte la dirección de todos los arcos.
4. Se transforma en un conjunto de reglas:
• Para cada nodo, se crea un símbolo no terminal de la gramática,
excepto para el etiquetado como A.
• Para cada arco etiquetado con a E ~T que va del nodo A E ~ N
al nodo B E ~N U {A} , se crea una producción A ::= B a.
• Si existe un arco del nodo del axioma al nodo de A, se crea una
regla S ::= A.
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 45
El algoritmo para realizar el paso inverso es similar al descrito.
Ejemplo: Supóngase la siguiente Gramática Lineal derecha.
GIO = ({O,l},{A ,B},A,P)
P = {(A ::= lB), (A ::= A) , (B ::= OA), (B ::= On
La Gramática Lineal izquierda equivalente se formará en los
siguientes cuatro pasos:
1. Se transforma la gramática de forma que no aparezca la A
en la parte derecha de la producción B ::= OA.
• Se crea un nuevo símbolo A'
• Se crean las reglas A' ::= lB y A' ::= A
• Se crea la regla B ::= OA'
• Se borra la regla B ::= OA.
La gramática queda como:
GlOl = ({O,l},{A,B, A'} , A,P)
P = {(A ::= lB), (A ::= A), (A' ::= lB), (A' ::= A),
(B ::= OA' ), (B ::= On
Como la gramática, por definición, no puede tener la regla
A' ::= A, ya que A' no es el axioma, se elimina dicha regla
y se sustituye la A' en todas las producciones en las que
aparezca en la parte derecha, quedando la gramática como:
GlOlI = {{O, l} , {A, B, A'}, A, P)
P = {(A ::= lB), (A ::= A), (A' ::= lB), (B ::= OA' ),
(B ::= O)}
2. Se crea un grafo que representa las transiciones de esta
gramática (figura 3.1).
3. Se invierte el grafo, tal como se muestra en la figura 3.2.
4. Se transforma el grafo en la siguiente gramática:
GlOlIl = ({O, l} , {A,B,A'} ,A,P)
P = {(A ::= BO), (A ::= A), (A' ::= BO) , (B ::= A'l),
(B ::= In
46 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS
Figura 3.1: Grafo construido a partir de la gramática G lO
Figura 3.2: Grafo construido a partir invertir el grafo en la fi!!UIa3. l.
3.2 Máquinas Secuenciales
Las Máquinas Secuenciales representan un tipo de autómata que es capaz
de, dada una palabra de entrada, generar otra palabra de salida. Para
ello, se definen un conjunto de estados, que "memorizan" la parte de la
palabra de entrada leída en cada momento y generan, al mismo tiempo que
transitan entre los estados, una salida. Se pueden ver como un autómata
que tiene dos cintas asociadas: una por la que va leyendo las palabras de
entrada, y otra de salida, en la que va generando la salida. En es a sección
se tratarán los aspectos básicos de este tipo de autómatas.
3.2.1 Definición
• Máquina finita de Mealy: es una quíntupla definida como
donde
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 47
~ E es el alfabeto de símbolos de entrada
~s es el alfabeto de símbolos de salida
Q es el conjunto finito no vacío de estados
f es la función de transición definida como:
f : Q x ~E ---+ Q
- 9 es la función de salida, definida como:
9 : Q X ~E ---+ ~s
Ejemplo: Supóngase la siguiente Máquina Secuencial, que
genera como salida una p en el instante t si hasta ese ins-
tante de tiempo ha recibido en la entrada un número par
de unos (considerando la entrada que no contiene ningún 1
como número par de unos), y genera una i en la salida si
hasta ese instante ha recibido un número impar de unos en
la entrada.
donde
Af1 = ({O,I},{p,i},{qO,ql},f,g)
f(qo, O) = qo
f(qo , 1) = ql
f(ql, O) = ql
f(ql, 1) = qo
g(qO, O) = p
g(qO , 1) = i
g(ql , O) = i
g(ql , 1) = P
-
48 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS
El comportamiento de las Máquinas Secuenciales es el si-
guiente: la máquina dispone de un conjunto de estados que
modelizan los diferentes momentos en los que puede estar
a la hora de resolver un problema. En este caso, hay dos
estados, qo, que simboliza el estado en el que, hasta ese ins-
tante, se han leído un número par de unos en la entrada. y
qI, que representa el hecho de que se han leído un número
impar de unos en la entrada. La función ¡ permite transitar
de un estado a otro en cuanto lee un 1 en la entrada (por-
que hay cambio de par a impar o viceversa), y transita al
mismo estado en el que se encuentre (no cambia de estado)
si se lee un 0, ya que no cambia la salida (de par a impar o
viceversa). La función g genera la salida correspondiente a
ese instante. En este caso, si está en el estado qo y lee un o.
sigue habiendo leído un número par de unos en la entrada.
con lo que generará una p en la salida. Esto es debido a
que, si está en el estado qo es porque hasta el momento de
leer el siguiente dígito de la entrada, había leído un número
par de unos, y si ahora lee un 0, el número de unos leídos en
la entrada no cambia y, por tanto, seguirá siendo par. Así
se razona con el resto de las salidas que genera la función g .
• Máquina finita de Moore: es una definición alternativa de Máquina
Secuencial en la que la función g sólo depende del estado en el que se
esté. La definición será:
MO = CEE, L.S, Q, ¡, g)
donde la única diferencia con respecto a la definición de Mealy es que
la función de salida g se define como:
g : Q -+ L.s
Ejemplo: Una Máquina de Moore que realiza la misma la-
bor que la MI definida anteriormente, sería:
M2 = ({O,l},{p,i},{qO,ql},¡,g)
donde
LENGUAJES, GRAMÁTICAS y A UTÓMATAS: UN ENFOQUE PRÁCTICO 49
f(qo , O) = qo g(qo) = P
f(qo, 1) = qi
f(qi, O) = qi g(qd = i
f(qi , 1) = qo
En el caso de las Máquinas de Moore, generan en la salida el
correspondiente símbolo del estado en el que estén después
de realizar cada tansición. Siempre que esté en el estado qo
genera una p en la salida, y siempre que esté en el estado
qi genera una i en la salida.
La diferencia fundamental entre los dos tipos de Máquinas Secuen-
ciales es que las ~áq~!!l_as_Q~Mealy suponen velocidad de proceso
infinita, ya que estas máquinas generan una salida inmediatamente
después de recibir la entrada, y, p-or" erconfiari¿~' las ' cleMoore supo-
nen una v~íocida,d finiÍa; ya, que la respuesta sólo dep~n:Qe~I~.~g.dQ
en el que se encu~J1t.r~J-ª- má<luina d~~i~~s q~.Jiªiii·a:r:cªQª trar.t¡¡ición.
3.2.2 Representación
Existen tres formas equivalentes de representar una Máquina Secuencial:
• Tablas de transición y de salida: se crea una matriz de IQI x I~E I
elementos para representar la función f y una matriz de IQI x I~E I
elementos (ó IQI para las Máquinas de Moore) para representar la g,
tal como se muestra en la figura 3.3. Los estados aparecen en las filas
de todas las tablas, mientras que los símbolos del alfabeto de entrada
aparecen en todas las tablas, menos en las tablas de la función de
salida de las Máquinas de Moore.
En el caso de las tablas que representan la función f, la posición
(qi, ej) está ocupada por el estado qk al que se transita en el caso
de que se esté en el estado qi y se lea en la entrada el símbolo ej.
En las tablas que representan la función de salida, la posición (qi, ej )
(o qi si es de Moore) está ocupada por el símbolo Sk que se genera
en la salida al estar en el estado qi y recibir en la entrada el símbolo
ej (o simplemente haber transitado al estado qi en las Máquinas de
Moore) .
Ejemplo: Las máquinas Mi y M2 definidas anteriormente
se representarían como:
--
50 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS~E ~E
Q I el I ... I em I Q I el I ... I em I
ql qi ... qj ql Si . .. Sj
.. . .. .
qn qk ... ql qn Sk . .. Sl
(a) f (b) gME
Figura 3.3: Ejemplos genéricos de tablas que representan la función de
transición f de una Máquina Secuencial (a), la función de salida 9 _\f E de
una Máquina de Mealy (b) o la función de salida gMO de una Máquina de
Moore (c), donde ei E ~E, qi E Q y sr E ~s ·
qo qo ql
ql ql qo
~E
Q lO 1 1 I
~
~
gMl
• Tabla única de transición y de salida: las dos funciones se pueden
representar en una sóla tabla, en la que, en las Máquinas de :\ Iealy,
en cada posición (qi, ej) aparecerá el estado al que se t ransita y la
salida correspondiente, si, estando en el estado qi se lee de la ent rada
el símbolo ej. En el caso de las Máquinas de Moore, las filas están
etiquetadas como Q /~s y el significado de las posiciones es el mismo
que en las tablas anteriores. La figura 3.4 muestra la representación
genérica.
• Diagramas de transición: son representaciones gráficas de las
Máquinas Secuenciales.
Mealy: se crea un grafo dirigido en el que
* para cada estado qi E Q se crea un nodo, y
* para cada transición f(qi,ej) = qk Y g(qi ,ej) = SI . se crea
un arco de qi a qk etiquetado con ej / SI
Moore: se crea un grafo dirigido en el que
* para cada estado qi E Q, si g(qd = Sj , se crea un nodo
etiquetado qd S j, y
LENGUAJES , GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 51
~E
Q I el l··· I em
ql qi/sp ... qj/Sr
.. .
qn qk/Ss ... qt!St qn/Sr qk q¡ ...J
(a) f/gME (b) f /gMO
Figura 3.4: Ejemplos genéricos de tablas únicas que representan la función
de transición y la de salida de una Máquina Secuencial de Mealy (a) , y de
una Máquina de Moore (b), donde ei E ~E , qi E Q y Si E ~s.
* para cada transición f (% ej) = qk, se crea un arco de qi a
qk etiquetado con ej.
Ejemplo: Las figuras 3.5(a) y 3.5(b) muestran la represen-
tación de las máquinas MI y M 2 utilizando diagramas de
transición.
l/í
O/p ~ Olí
C6J @~
~
l/p
(a) (b)
Figura 3.5: Diagramas de transición de la Máquina de Mealy MI (a) y la
de Moare M 2 (b)
3.2.3 Extensión a palabras de la entrada y salida
En lugar de tratar uno a uno los símbolos de la entrada y generar uno a uno
los símbolos de salida, se va a estudiar cómo se puede tratar una secuencia
seguida de entradas y generar la salida correspondiente por medio de una
extensión de las definiciones anteriores.
-
52 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS
Extensión de Mealy
La función de transición f se redefine como:
f: Q x ~E -+ Q
Además,
f(q , ax) = f(J(q, a), x) para cada q E Q, a E ~E , x E ~E
f(q, >') = q para cada q E Q
donde >. es la palabra vacía. Es decir, para una palabra formada por
varios símbolos, el estado al que transita la Máquina Secuencial es el co-
rrespondiente a transitar con cada uno de los símbolos.
La función de salida, g, se redefine como:
g: Q x ~E -+ ~s
y, a las salidas anteriores, se les añaden las siguientes salidas correspon-
dientes a palabras de longitud cero o mayor que uno:
g(q, ax) = g(q, a) . g(J(q, a) , x) para cada q E Q, a E ~E , X E ~E
g{q, >') = >. para cada q E Q
La salida que se genera es la correspondiente a concatenar la salida
producida con cada uno de los símbolos de la entrada y sus transiciones.
Ejemplo: Si la palabra de entrada es 01001 y la máquina MI
comienza en el estado qo , MI generaría el siguiente comporta-
miento en cuanto a transiciones y salida:
f(qo, 0100) = f(J(qo, 0),100) = f(qo, 100) = f(J(qo, 1) , 00) =
= f(qI, 00) = f(J(qI, O), O) = f(qI, O) =
f(f(qI,O),>.) = f(qI,>') = qI
y, al mismo tiempo:
g(qO , 0100) = g(qO , O)g(J(qO, 0) , 100) = pg(qO , 100) =
pg(qO, 1)g(f(qo , 1) ,00) =
pig(qI, 00) = pig(qI, O)g(J(qI , O), O) = piig(qI , O) =
piig(qI, O)g(J(qI, O), >') = piiig(qI, >') = piii
LENGUAJES, GRAMÁTICAS y AUTÓMATAS: UN ENFOQUE PRÁCTICO 53
Extensión de Moore
Se redefinen f y 9 de la misma forma que para las Máquinas de Mealy.
• f: Q x ~E -+ Q
• g: Q -+ ~s
Pero se añade una nueva función de salida de palabras g' definida como:
g' : Q x ~E -+ ~s
También se cumplen las siguientes igualdades:
• f(q, ax) = f(J(q, a), x) (Vq E Q, a E ~E, X E ~E)'
• f(q, A) = q (Vq E Q)
• g'(q ,ax) = g(q) . g'(J(q,a) , x), (Vq E Q, a E ~E, X E ~E)
• g'(q, A) = A (Vq E Q)
donde, a la hora de calcular la función de salida, g', de una palabra
se utiliza la función de salida, g, de un único símbolo. Hay que tener en
cuenta que a la hora de calcular la función salida, hay que realizar primero
la transición. Así, la primera salida será la correspondiente al estado al que
se llega desde el estado inicial y el primer símbolo de la entrada.
Ejemplo: Si la máquina M 2 recibe como entrada la palabra
01001 y comienza en el estado qo , generaría el siguiente com-
portamiento en cuanto a transiciones y salida:
f(qo,0100) = f(f(qo,0),100) = f(qo,100) = f(f(qo,l),OO) =
f(qI,OO) = f(J(qI, O), O) = f(qI, O) =
f(f(qI,O),A) = f(qI,A) = qI
y, al mismo tiempo:
g'(qo,0100) = g(qo)g'(J(qO, 0),100) = pg'(qO, 100) =
pg(qI)g'(J(qO , 1),00) =
pig'(qI, 00) = pig(qdg'(J(qI , O), O) = piig'(qI, O) =
piig(q¡)g'(f(qI, O), A) = piiig'(qI , A) = piii
-
54 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS
Función respuesta de una Máquina Secuencial
A partir de las funciones de salida y con el objetivo de unificar los dos
tipos de Máquinas Secuenciales, se define una función respuesta, h, de la
siguiente forma:
Vq E Q, x E ~E, h(q, x) = { g~(q, x))
g q,x
si es de Mealy
si es de Moore
Dada esa nueva función, en cada Máquina Secuencial se cumplen los
siguientes teoremas:
• Vq E Q, x E ~E' Ih(q, x)1 = Ixl
• Vq E Q, x, y E ~E' f(q, xy) = f(f(q, x), y)
• Vq E Q, x, y E ~E' h(q, xy) = h(q, x) . h(f(q, x), y)
Ejemplo: Dada la máquina MI , se define la h(q, x) = g(q , x)
Vx E {O, 1} * ,q E {qo, ql}. Entonces, se cumplen, entre otras ,
las siguientes igualdades (provenientes de los teoremas):
• Ih(qo, 0100)1 = 101001 = 4, lo cual se cumple al ser
h(qo, 0100) = g(qO , 0100) = piii
• f(qo, 0100) = f(f(qo, 01) , 00)
Por una parte, f(qo,0100) = ql como se ha mostrado en
ejemplos anteriores. Por otra parte,
f(f(qo,Ol),OO) = f(f(f(qo,O), 1),00) = f(f(qo , 1) , 00) =
f(ql , 00) = f(f(ql , O) , O) = f(ql , O) =
f(f(ql,O) , A) = f(ql,A) = ql
• h(qo , 0100) = h(qo, 01)f(f(qo, 01), 00)
Por una parte, h(qo , 0100) = piii como se ha mostrado en
ejemplos anteriores. Por otra parte,
L ENGUAJES , GRAMÁTICAS y A UTÓMATAS: UN ENFOQUE PRÁCTICO 55
h(qo,OI)h(f(qo,OI),OO) = h(qo ,O)h(f(qo ,O) , I)h(f(qo , OI) ,OO) =
ph(qo, l)h(ql,OO) =
pih(ql,O)h(f(ql,O),O) =
piih(ql , O) = piih(ql, O)h(f(ql , O) , >.) =
piiih(ql, >.) = piii c.q.d.
3.2.4 Equivalencia de Máquinas Secuenciales
Dadas dos Máquinas Secuenciales es importante saber si, dadas las mismas
palabras de entrada generan la misma salida; es decir, si son equivalentes.
Para poder analizar cuándo dos máquinas son equivalentes, se van a definir
primero unos conceptos básicos.
Definiciones
• Equivalencia de estados: dos estadosql, q2 E Q son equivalentes,
qlEq2 , si para cada palabra x E ¿:E se cumple que la salida generada
comenzando por ql y recibiendo x como entrada, genera la misma
salida que comenzando por q2 y recibiendo x como entrada:
h(ql ,X) = h(q2,X )
Ejemplo: Dada la siguiente Máquina Secuencial:
A/3 = ({0 , 1} , {p ,i}, {qO , ql , q2} , f , g)
donde f y 9 serán:
f(qo, O) = q2
f(qo , 1) = ql
f(ql , O) = ql
f(ql, 1) = qo
f(q2 , O) = qo
f(q2 , 1) = ql
g(qO, O) = p
g(qo, 1) = i
g(ql, O) = i
g(ql, 1) = P
g(q2 , O) = P
g(q2 , 1) = i
....
56 CAPÍTULO 3. GRAMÁTICAS REGULARES y AUTÓMATAS FINITOS
Los estados qo y q2 son equivalentes (qOEq2)' Pese a que no
se va a demostrar formalmente, esto es debido a que, para
cualquier palabra formada con los símbolos del alfabeto de
entrada, la salida es la misma empezando en cualquiera de
los dos estados. Así, por ejemplo:
y
Lemas
Continuar navegando
Materiales relacionados
28 pag.
106 pag.
84 pag.Busquedas-en-texto-con-expresiones-regulares
Cursando Fisica Matematica
27 pag.
Preguntas relacionadas
Compartir