Introducción a la teoría de gramáticas. Lenguajes y autómatas (página 2)

En el campo de la informática, el concepto de
Gramática Formal adquirió gran
importancia para el desarrollo de
lenguajes de
programación, consiguientemente el desarrollo de
autómatas y maquinas de Turing cobró vida en las
últimas décadas, fortaleciendo el vínculo
entre Electrónica e Informática, creando
máquinas cada vez mas sofisticadas y menos
complicadas para el usuario final.

El propósito de este material está dirigido a
introducir a los estudiantes universitarios de las ramas de la
Informática, en el fascinante mundo de los lenguajes y la
lógica
implícita en las máquinas del siglo XXI.
Proporcionando una guía práctica con ejercicios
resueltos que pretenden fortalecer el
conocimiento de la teoría
de gramáticas y lenguajes formales, en el entendido que
cada solución propuesta en este material, no representa la
única solución, existiendo muchas maneras de
resolver el mismo ejercicio.

CAPÍTULO I

CONCEPTOS Y
DEFINICIONES

Veamos algunos conceptos que nos permitirán
conceptualizar la gramática

SÍMBOLO

Es una entidad abstracta, que no se va a definir. Normalmente
los símbolos son letras (a,b,c,…z),
dígitos (0,1,2…9) y otros caracteres
(+,*,/,-,?…).

Un símbolo también puede estar formado por
varias letras o caracteres, como las palabras reservadas de un
lenguaje de
programación son símbolos de dicho lenguaje.
Ejemplo:

-   a,b,c,#,+,-,*, then, begin, end, else,
…

VOCABULARIO O ALFABETO

Un vocabulario o alfabeto es un conjunto finito de
símbolos, no vacío. Para definir que un
símbolo a pertenece a un alfabeto V, se
utiliza la siguiente notación aÃŽV.

Los alfabetos se definen por enumeración de los
símbolos que contienen, podemos ver los siguientes
ejemplos:

·   V1={A,B,C,D,E,F,…..,X,Y,Z}

·   V2={a,b,c,d,0,1,2,3,4,*,#,+}

·   V3={0,1}

·   V4={if, then, begin, end, else,
a,b,;,=,>}

·   También se pueden definir las
tablas ASCII y EBCDIC
como los alfabetos de distintos ordenadores.

CADENA

Una cadena es una secuencia finita de símbolos de un
determinado alfabeto.

Ejm. Tomando en cuenta los alfabetos o vocabularios definidos
anteriormente, podemos decir que:

abcb es una cadena del alfabeto V2

a+2*b es una cadena del alfabeto V2

000111 es una cadena del alfabeto V3

If a>b then b=a; es una cadena del alfabeto V4

LONGITUD DE CADENA

La longitud de una cadena consiste en el número de
símbolos pertenecientes a la cadena. Ejm. Tomando en
cuenta los ejemplos de cadena podemos decir que:

·   |abcb| es de longitud 4

·   |a + 2*b| es de longitud  5

·   |000111| es de longitud  6

·   |if a>b then a=b;| es de longitud
 9

CADENA VACÍA

Se denomina cadena vacía, que no tiene símbolos
y se denota con l, por lo que su longitud es :

| l | ® 0

CONCATENACIÓN DE CADENAS

Sean A y B dos cadenas cualesquiera, se denomina
concatenación de A y B a una nueva cadena AB constituida
por los símbolos de la cadena A seguidos por los de la
cadena B.

El elemento neutro de la concatenación es l:

A l =  lA = A

UNIVERSO DEL DISCURSO

El conjunto de todas las cadenas que se pueden formar con los
símbolos de un alfabeto, se denomina universo del
discurso V
y se representa por W(V). Evidentemente W(V) es un conjunto
infinito. La cadena vacía pertenece a W(V).Ejm:

Sea un alfabeto con una sola letra V={a}, entonces el universo del
discurso es:

W(V) = {l, a, aa, aaa, aaaa, ….}

que contiene infinitas cadenas.

GRAMÁTICA

Veamos algunos conceptos que nos ayuden a formular el concepto
de gramática:

(Del lat. grammatĭca, y este del gr.
γραμματική). f.
Ciencia que
estudia los elementos de una lengua y sus
combinaciones. Arte de hablar y
escribir correctamente una lengua. Estudio de una lengua regido
por el principio de que todos sus elementos mantienen entre
sí relaciones sistemáticas. La que trata de
formular una serie de reglas capaces de generar o producir todas
las oraciones posibles y aceptables de un idioma o
lenguaje

Microsoft® Encarta® 2007. © 1993-2006 Microsoft
Corporation. Reservados todos los derechos.

Una definición un tanto técnica: " La
gramática es un ente formal para especificar, de una
manera finita, el conjunto de cadenas de símbolos que
constituyen un lenguaje" . La gramática genera o describe
un lenguaje.

AUTÓMATA

(Del latin. automăta, t. f. de
-tus, y este del gr.
αὐτόματος,
espontáneo). m.Instrumento o aparato que encierra dentro de
sí el mecanismo que le imprime determinados movimientos o
respuestas. Máquina que imita la figura y los movimientos
de un ser animado. Microsoft® Encarta® 2007. ©
1993-2006 Microsoft Corporation. Reservados todos los
derechos.

En el caso de los Procesadores de Lenguaje un
autómata es una construcción lógica que recibe como
entrada una cadena de símbolos y produce una salida
indicando si dicha cadena pertenece o no a un determinado
lenguaje.

LENGUAJE

Conjunto de sonidos articulados con que el hombre
manifiesta lo que piensa o siente. Sistema de
comunicación verbal. Manera de expresarse.
Conjunto de señales
que dan a entender algo. El lenguaje de
los ojos, el de las flores. En Informática Conjunto de
signos y
reglas que permite la
comunicación con un ordenador. Microsoft®
Encarta® 2007. © 1993-2006 Microsoft Corporation.
Reservados todos los derechos.

Podemos expresarlo de manera más sencilla como un
conjunto de palabras ó cadenas de símbolos
(palabras, oraciones, textos o frases) de un determinado
alfabeto.

LENGUAJE VACÍO

Existe un lenguaje denominado lenguaje vacío,
que es un conjunto vacío y que se denota por {Ø}.
El lenguaje vacío no debe confundirse con un lenguaje que
contenga una sola cadena, y que ésta sea la cadena
vacía, es decir {l}, ya que el número de elementos
(cardinalidad) de estos dos conjuntos es
diferente.

Cardinal ({ Ø }) = 0

Cardinal ({ l }) = 1

PALÍNDROMOS

Cadenas que se leen igual hacia delante, que hacia
atrás. Por ejemplo, ORURO

CAPÍTULO II

LENGUAJES Y
GRAMÁTICAS

LENGUAJE

Se denomina lenguaje a un conjunto de palabras de un
determinado alfabeto.

También un lenguaje es un conjunto de cadenas de
símbolos (palabras, oraciones, textos o frases).

Un lenguaje está compuesto por Sintaxis:
(gramática), que define las secuencias de símbolos
que forman cadenas válidas de un lenguaje. Y por
Semántica, que es el significado de las cadenas que
componen un lenguaje.

Ejemplo 1:

Sintaxis: A

Semántica: es un número natural.

Diferente sintaxis en diferentes lenguajes:

           
A: natural

 
          A: es
un número que pertenece al conjunto de |N={1,2,3..N}

Ejemplo 2:

   Sintaxis:

           
if a=b then write(a, " es igual a ", b )

                      
else write(a, " es distinto a ", b )

   Semántica:

Si se cumple la condición entonces se muestra un
mensaje que ambos números son iguales.

Caso  contrario, se escribe los número son
distintos.

Gramática

Chomsky la define como: " Descripción formalizada de las oraciones de
un lenguaje. Una gramática genera o describe
un lenguaje."

DEFINICIÓN FORMAL DE GRAMÁTICA

Una gramática es una cuádrupla:

                       
G = (VT, VN, S, P)

donde:

VT= {conjunto finito de símbolos terminales}

VN={conjunto finito de símbolos no terminales}

S es el símbolo inicial y pertenece a VN

P= {conjunto de producciones o de reglas de
derivación}

Todas las cadenas del lenguaje definidas por la
gramática están formadas con símbolos del
vocabulario terminal VT. El vocabulario terminal se define
por enumeración de los símbolos terminales.

El vocabulario no terminal VN es el conjunto de
símbolos introducidos como elementos auxiliares para la
definición de la gramática, y que no figuran en las
sentencias del lenguaje.

La intersección entre el vocabulario terminal y no
terminal es el conjunto vacío:

{VN} Ç {VT} = {Ø}

La  unión entre el vocabulario terminal y no
terminal es el vocabulario.

{VN} È {VT} = {V}

En ocasiones es importante distinguir si un determinado
vocabulario incluye o no la cadena vacía,
indicándose respectivamente con superíndice + o
superíndice *, tal como se muestra a
continuación:

V+ = V – {l}

V* = V + {l}

El símbolo inicial S es un símbolo no
terminal a partir del cual se aplican las reglas de la
gramática para obtener las distintas cadenas del
lenguaje.

Las producciones P son las reglas que se aplican desde
el símbolo inicial para obtener las cadenas del lenguaje.
El conjunto de producciones P se define por medio de la
enumeración de las distintas producciones, en forma de
reglas o por medio de un metalenguaje.

Ej 1: Sea la gramática: G=(VT,VN,S,P) donde VT={a,b},
VN={S} y el conjunto de producciones es:

                       
S ® ab

                       
S ® aSb

Las cadenas de esta gramática están dadas por:
ab, aabb, aaabbb,
aa…anbb….bn

Ej 2. Sea la gramática: G=({a,b,c,d}, {S,A,B},S,P)
donde P son las producciones:

                       
S ® ASB

                       
A ® b

                       
aaA ® aaBB

                       
S ® d

                       
A ® aA

                       
B ® dcd

Las cadenas de esta gramática son: bddcd, abddcd,
aabddcd, bbaddcddcddcd……

Ej 3: Sea la gramática: G=(VN, VT,S,P) donde:

           
VN={<número>, <dígito>}

           
VT={0,1,2,3,4,5,6,7,8,9}

           
S= <número>

Las reglas de producción P son:

           
<número>::=<dígito><número>

           
<número>::=<dígito>

           
<dígito>::=0| 1| 2| 3| 4| 5| 6| 7| 8| 9

DEFINICIÓN FORMAL DE LENGUAJE

El lenguaje L (G) generado por una gramática G es el
conjunto de todas las sentencias que puede generar G. Es decir
expresado formalmente:

                       
L (G) = {hÃŽVT*/S ® h}

Una sentencia pertenece a L (G) si:

-    h son símbolos terminales (VT)

-    La sentencia puede derivarse del
símbolo inicial S aplicando las reglas de
producción de la gramática

PROPIEDAD

Dos gramáticas son equivalentes si ambas generan el
mismo lenguaje.

G1 y G2 son equivalentes si L(G1) = L(G2)

EJEMPLO 1:

Sea la gramática definida por

G1= ({S}, {0,1},S,P)

donde

P={(S® 000S111), (0S1 ®01)} .

Determinar el lenguaje que genera.

SOLUCIÓN

La única forma de generar sentencias es aplicando
cualquier número de veces la primera producción y
terminado con la aplicación de la segunda, así se
obtiene el lenguaje.

S ®000S111 ®000000S111111 ®
…..®0(3n-1)0S11(3n-1)
®0(3n)1(3n)

Por consiguiente el lenguaje que genera esta gramática
es el conjunto infinito de instrucciones que se indica a
continuación:

L(G2)={0(3n)1(3n)/n>=1}

Si la 2ª producción de la gramática del
ejemplo 1 fuese S®01 el lenguaje sería:

SOLUCIÓN

L(G2)={0(3n+1)1(3n+1)/
n>=0}

EJERCICIOS RESUELTOS

1. Sea la gramática definida por

           
G1= ({S},{a,b},S,P)

Donde:

P={(S® aSb), (S® ab)}

Determinar el lenguaje que genera.

SOLUCIÓN

L(G1)={anbn/
n>=1}

2. Dadas las siguientes palabras del lenguaje determinar las
reglas de producción que las genera.

yxxyx

x

xyyx

(xyy)nx

(yxxy)nx

SOLUCIÓN

G2= ({S,A}, {x,y},S,P)

donde P={(S® xyAS),(xyA ®yxxy)(S® x),(A®
y)}.

L(G2)={cadenas que contienen xyy y yxxy
intercambiándose y reproduciéndose cualquier
número de veces, y terminado siempre con el símbolo
x}

CAPÍTULO III

JERARQUÍA DE LAS
GRAMÁTICAS

Para una mejor comprensión las gramáticas han
sido clasificadas de acuerdo a particularidades y restricciones
propias, una de ellas y la más acertada es la formulada
por Avram Noam Chomsky, quien clasificó las
gramáticas de acuerdo a cuatro tipos, dando origen a la
Jerarquía de Chomsky en función de
la forma de reglas de derivación o producción.

Las gramáticas no restringidas   Tipo 0

Sensibles al
contexto               
           
Tipo 1

Independientes del
contexto      
           
Tipo 2

Gramáticas regulares   
                       
Tipo 3

La clasificación comienza con un tipo de
gramáticas que pretende ser universal, aplicando
restricciones a sus reglas de derivación, se van
obteniendo los otros tres tipos de gramáticas. Esta
clasificación es jerárquica, es decir cada tipo de
gramática incluye a todos los tipos siguientes.

Los lenguajes que resultan de dichas gramáticas
también se identifican con lenguajes de tipo cero, uno,
dos y tres.

A esta jerarquía de lenguaje se le conoce como la
jerarquía de chomsky.

GRAMÁTICAS TIPO 0

También llamadas gramáticas no restringidas
con estructura de
frase. Se caracterizan por:

• En la parte izquierda tiene que haber al menos un
  símbolo no terminal.
• Respecto a sus partes derechas de producciones no hay
  ningún tipo de restricción.
• Las reglas de derivación son de la forma:

b®a

• Siendo a ÃŽ(VN È VT)+  
  y Îb (VN È VT), es decir la
  única restricción es que no puede haber reglas de
  la forma

l®b

           
donde l  es la cadena vacía.

• Ejemplos de estas gramáticas son todos los
  ejercicios que hemos visto hasta ahora.

EJEMPLO

• Sea la gramática definida por: G= ({S},
  {0,1},S,P)

donde

P={(S® 000S111), (0S1 ®01)} .

Determinar el lenguaje que genera.

SOLUCIÓN

L(G)={0(3n+1)1(3n+1)/
n>=0}

GRAMÁTICAS TIPO 1

También llamadas gramáticas sensibles al
contexto. Es decir que es importante tomar en cuenta la
ubicación de los símbolos no terminales en la regla
de derivación (que preceden y suceden a cada
símbolo Terminal, deben mantener su ubicación en el
lado derecho de la regla de producción tal como aparece en
la parte izquierda de la regla de producción).

En este tipo de gramática sus reglas de
producción son de la forma:

aAb ®
bga

Siendo A ÃŽ VN

a, b Î (VN È VT) * y

gÎ (VN È VT)*

Estas gramáticas se llaman sensibles al contexto, pues
se puede reemplazar A por g siempre que estén en el
contexto a….b.

EJEMPLOS

• La gramática G=({S,A,B}, {a,b}, S, P) cuyas
  producciones P se muestran a continuación:

S ® aB

B ® bAb

bA®bcD

cD ®cAA

A ®aaA

A ®b

PROPIEDADES DE LAS GRAMÁTICAS TIPO 1

• Propiedad de no decrecimiento.- Las cadenas que se
  obtienen en cualquier derivación de una gramática
  de tipo 1 son de longitud no decreciente, es decir:

a®b Þ
êbê³ êaô

           
 Y se puede enunciar como la longitud de la parte derecha de
la producción es mayor o igual a la parte izquierda. Es
decir no tiene reglas compresoras.

Se puede demostrar de la siguiente manera:

aA b ® bga

   Siendo ÃŽg (VNÈVT)+, es
decir g nunca puede ser la cadena vacía, lo que implica
que ôgô³1 y como |A| como mínimo vale 1,
queda demostrada la propiedad:

ôaAb| <= |agbô

• Propiedad de sensibilidad al contexto

En los lenguajes generados por estas gramáticas el
significado de las " palabras" depende de su posición en
la frase.

A los símbolos a y b es a lo que se llama
contexto. Es decir, A sólo puede
transformarse en  g si va precedido de a y seguido de b.

Ejercicio 1.

• Dado el siguiente lenguaje elabora las reglas de
  producción

L(G) = {
0n1n / n ≥
1}

Solución

G = { {S, A}, {0, 1}, S, P
}

Reglas de producción:

 S → 0SA / 01

 1A → 11

Ejercicio 2

• Construye una gramática tipo 1 que genere el
  lenguaje    

L = {a(bc)n / n > = 1}

Solución

           
S→ aB

B → bc B / bc

GRAMÁTICAS TIPO 2

• También se denominan gramáticas de
  contexto libre o libres de contexto.
•  Sus reglas de producción tan sólo
  admiten tener un símbolo no terminal en su parte
  izquierda, es decir son de la forma:

A ® a

Siendo A ÃŽ VN y ÃŽa (VN
È VT) +

Si cada regla se representa como un par ordenado (A, a), el
conjunto P es un subconjunto del conjunto producto
cartesiano VN x ({VN È VT}) +, es decir:

PN{Ì x ({VN} È {VT})+}

La denominación contexto libre se debe a que se puede
cambiar A por a, independientemente del contexto en que aparezca
A.

EJEMPLOS

Ejemplo 1

• La gramática G=({S,A,B}, {a,b}, S, P) cuyas
  producciones P se muestran a continuación es de tipo
  2:

S ® aB

S ® bA

A®a

A ® aS

A ®bAA

B ®b

B ®bS

B ®aBB

Ejemplo 2

• La gramática G=({a,b}, {A,S}, S,P) donde P son las
  producciones que se muestran a continuación es de tipo
  2.

S ®aS

S ®aA

A ®bA

A ®b

Ejercicio 1.

• Dado el siguiente lenguaje  L(G) = {
  0n1n / n
  ≥ 1}

Con las siguientes reglas de producción tipo 1.
Convertir a tipo 2

• Reglas de producción:

 S → 0SA / 01,

 1A → 11

Solución

S → 0S1 / 01

Ejercicio 2

• Construye una gramática tipo 2 que genere el
  lenguaje:

L = {a(bc)n / n > = 1}

Solución

S→ aB

B → bc B / bc

GRAMÁTICAS TIPO 3

• También denominadas regulares o
  gramáticas regulares a la derecha comienzan sus
  reglas de producción por un símbolo terminal que
  puede ser seguido o no por un símbolo no terminal, es
  decir son de la forma:

A ® aB

A ® a

Donde A, B ÃŽ VN y aÃŽ VT

EJEMPLO

Sea la gramática:

      G=({a,b}, {A,S}, S, P)

donde P son las producciones formuladas por:

S ® aS

S ® aA

A ® bA

A ® b

 Ejercicio 1

Construye una gramática tipo 2 que genere el
lenguaje:

L = {a(bc)n / n > = 1}

Solución:

S ® aB/a

B ® bC/bc

C® cB

CAPÍTULO IV

EJERCICIOS
RESUELTOS

1. Construye una gramática tipo0 que genere las
cadenas V* que no contengan la secuencia " abc"

Solución:

S ® aB/bB/cB/dB

B ® bB/dB/l

B® aC/dC/l

C® dD/aC/aD/l

D® cD/dD/aD/l

B® bbC

2. Construye una gramática tipo 0 para el siguiente
lenguaje:

L(G)={anbm /
n>=4,m>=3}

Solución:

S ® aaaa/A

A ® aA/b/bb/bbb/l

3. Construye una gramática para el vocabulario V=
{a,b,c,d} donde todas las cadenas generadas contengan una
única a.

Solución:

S ® aB/Ba

S ® bC/cC

B® bB/cB/l

C® bC/cC/a/Cb/Cc

4. L = {xc3m/ x {a,
b}* y la cantidad de b"s es par y m
0}

Solución:

S ® aA/bbA

A ® aA/bbA/C/ cccC

C® cccC /ccc

5. Construye una gramática para el siguiente
lenguaje:

L(G)={bnan+1c
n+2 / n>=1}

Solución:

S ® bBaAcc

B ® a / bBaA

aAa ® aaA

Ac ® cc

Aa ® aA

6. Construye una gramática para el siguiente
lenguaje:

L(G)={anc b m / n>0 y
m>=0}

Solución:

S ® aAcB

A ® aA /l

B ® bB/l

7. Construye una gramática para el siguiente
lenguaje:

L(G)={00X1 / X ÃŽ {0,1}*
}

Solución:

S ® 00X1

X ® 0X/ 1X /l

8. Construye una gramática para el siguiente
lenguaje:

L(G)={X c3m / X ÃŽ
{a,b}* y la cantidad de b"s es par y m>=0}

Solución:

S ® AC

A ® aA /bbA/ l

C ® cccC/l

9. Construye una gramática para el siguiente
lenguaje:

L(G)={X/ X ÃŽ {0,1}* y X contiene
la subcadena 00 ó X contiene 11}

Solución:

S ®  X00X/ X11X

X ® 0X / 1X/ l

10. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que finalicen con b y que no tengan 2
b"s consecutivas.

Solución:

S ® b/ baAb/aAb

A ® aA /abA/a/ l

11. Construye una gramática que genere cadenas del
alfabeto {a,b} que finalicen con  ba

Solución:

S ® Aba

A ® aA/ bA /l

12. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que no tengan 2 a"s consecutivas.

Solución:

S ® abA/bAB

A ® abA/bA/a/b/l

A ® baB

B ® baB/b

13. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que genere el lenguaje:

 L(G)={an b n /donde n
sea múltiplo de 4}

Solución:

S ® aaaaAbbbb

A ® aaaaAbbbb/l

14. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que genereun número par de aes

Solución:

S ® aaAbB/ bBAaa/baAaB/abBaA

A ® aaA/ l

B ® bB/ l

15. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que genere un número par de aes y un
número impar de bes.

Solución:

S ® aaAbB

A ® Aaa

B ® bbB/ C

C ®l

16. Construye una gramática que genere cadenas del
alfabeto V=(a,b) donde a sea siempre par

Solución:

S ® AB/ BA

A ® aaA/ bA/l

17. Construye una gramática que genere cadenas del
alfabeto V=(a,b) que genere un número impar de
aes.

Solución:

S ® AB/BA

A ® aC

C ® aaC/ l

B ® bB

18. Construye una gramática que genere cadenas del
alfabeto V=(a,b) en la que cada instancia del símbolo a
esté precedida y seguida de al menos una instancia de b.
Ejm: bab, babab, bbabbbabbbb.

Solución:

S ® BaB/ ABaB/ B

B ® bB/ b

A ® baA/ b

19. Sea el vocabulario V=(a,b) y la expresión
aa*bb*. Indicar el lenguaje que denota y algunas cadenas de dicho
lenguaje.

ab

aab

aaaab

abbbb

abb

aaab

Solución:

L={cadenas que comienzan por una a y continúan con
varias o ninguna a, y siguen con una b y continúan con
varias o ninguna b}

20. Construye una gramática tipo 0 y tipo 1 que
genere el siguiente lenguaje:

L(G)={cn+2 a n+1 c n
/n>=1}

Solución Tipo 0

S ® ccAaBc

B ® a/AaBc

aAa ® Aaa

Ca ® cc

aA ® Aa

Solución Tipo 1

S ® ccCaAD/ cccaac

C ® cCAD

DA ® XA

XA ® XY

XY ® AY

AY ® AD

aA ® aa

Da ® DZ

DZ ® DN

DN ® NM

NM ® ZD

ZD ® aD

CA ® ca

DD ® cc

CD ® cc

21. Construye una gramática que genere el siguiente
lenguaje:

L(G)={anb mc /m>=0,
n>=1, m múltiplo de 3, n par}

Solución:

S ® ABc/ Ac

A ® aaA/ aa

B ® bbbB/ bbb

22. Construye una gramática que genere cadenas de
V=(a,b) que no contengan 3 aes consecutivas

Solución:

S ® AB/BA

A ® aB/aaB/a

B ® bB/bA/b

23. Construye una gramática  que genere el
siguiente lenguaje:

L(G)={cn a n+1 c
n+2 /n>=1}

Solución:

S ® cBaAcc

B ® a/cBaA

aAa ® aaA

Ac ® cc

Aa ® aA

24. Para cada una de los siguientes incisos, proporcione,
si es posible, una gramática tipo 3 que defina el mismo
lenguaje. Si en algún caso no es posible
justifique.

a) ab* / ba*

Solución:

S ® a / b /  aA/ bB

A ®  bA/ b

B ®  aB/  a

b) (a | b)*c

Solución:

S ®  c/  aS/ bS
c) b*a / a*b

Solución:

S®  a / b / bA/ aB

A®  bA/ a

B ®  aB/ b

25. Dada la siguiente gramática  cuyas reglas
de producción son de la forma:

 P={S ®A, S ® b B b, A ® b C, A ®
a S B, B ® c C, B ® a, C®
c C, C ® b A}.

Se pide:

a) Razone si es posible que una cadena del lenguaje que define
esta gramática empiece por el símbolo a y
termine por el símbolo b. Argumente su
respuesta.

b) Razone si es posible que una cadena del lenguaje que define
esta gramática empiece por el símbolo b y
termine por el símbolo a. Argumente su
respuesta.

Solución:

a) Ninguna cadena del lenguaje definido por la
gramática dada puede comenzar por el símbolo
a y terminar por el símbolo b. Todas las
reglas de producción de la gramática, excepto S
® bBb y B ® a terminan por A, B o C.
Por lo tanto, comenzando la derivación utilizando S ®
A, las formas sentenciales que se obtienen siempre terminan por
A, B o C,  por lo que inevitablemente llegamos a cadenas que
terminan por a. Teniendo en cuenta que comenzando la
derivación utilizando S ® bBb se
obtienen cadenas que empiezan por b, se concluye que no es
posible que una cadena del lenguaje dado cumpla con la
condición antes mencionada.

b) Por otra parte, la cadena bbababa pertenece al
lenguaje, luego es posible que una cadena del lenguaje que define
esta gramática empiece por el símbolo b y
termine por el símbolo a.

26. Dado el siguiente lenguaje, defina la gramática
tipo 2 que lo genera.

  L = {am bn
ck | m > n + k ; n, k >=0}

Solución:

Se puede desglosar de la siguiente manera:

L = {am ak an
bn ck / m > 0; n, k >=0 }

S ® AB

A® aA /a

B ® aBc /C

C ® aCb /ab

27. Dado el conjunto de palabras, determine la
gramática y el lenguaje que las genera.

 bcc, abccc, abbccccc, aabcccc, aabbcccccc,
aaaaabccccccc,……..

Se pide:

a) Definir un lenguaje mediante reglas de
producción.

b) Demostrar con ejemplos las posibles derivaciones de S.

Solución:

V= {a, b, c}, L = {an bm
cn+2m | n >=0, m >= 1}

S ® aSc | A

A ® bAcc | bcc

28. Escribe la gramática tipo 1 que genere el
siguiente lenguaje:

L = {an bm c / n>=1, m>=
0;  n es múltiplo de 3 y m es par }

Solución:

S ® ABc/ Ac

A ® aaaA/aaa

B ® bbB/bb

29. Escribe la gramática tipo 1 del alfabeto {a, b}
que contengan como subcadena 3 aes consecutivas.

Solución:

S ® aaaA/AaaaA/aaa/Aaaa

A ® aA/a/ b/ bA

30. Dado el vocabulario V= {a, b}, escribe la
gramática tipo 2 que genere el siguiente lenguaje:

L = { anbm | m <= n <= 2m
; n, m >=0}

Solución:

S ® aSb | aaSb | ab

31. Escribe la gramática o reglas de
producción tipo 0 que generen el siguiente
lenguaje:

L = { anbm | n  <> m
; n, m >0}

Donde el símbolo <> significa distinto.

Solución:

Podemos desglosar el lenguaje de la siguiente manera:

L = { anbm | n > m ; n, m
>0} È { anbm | n
< m ; n, m >0}

                       
S ®  A / B

                       
A ® aAb / aA /aab

                       
B ® aBb /Bb /abb

Bibliografía

·   Alfonseca, M., J. Sancho, M. A. Orga,
Teoría de Lenguajes, Gramáticas y
Autómatas, Promosoft, 1997.

·   Cueva L., Juan Manuel, Lenguajes
Gramáticas y Autómatas, Segunda Edición, 2001, Universidad de
Oviedo.

·   Díaz Víctor, Cañete
José Miguel, Lenguajes Formales y autómatas,
Universidad de Sevilla, 2006

·   Ferreiro, Emilia y Margarita Gómez
Palacio (Comp.) Nuevas perspectivas sobre los procesos de
lectura y
escritura.
Siglo XXI. Buenos Aires.

·   H. Contreras, Los fundamentos de la
gramática transformacional, México, siglo XXI,
1971.

·   Hopcroft, J.E., R. Motwani, J. D. Ullman,
Introducción a la teoría de
autómatas, lenguajes y computación (2ª
Edición), Prentice-Hall, 2000.

·   J. Nivette: Principios de
gramática generativa. Madrid, Fragua, 1973.

·   Vidal Lamiquiz, Lingüística Española.
Publicaciones de la Universidad de Sevilla, 1973.

Autores

Autor:

Lic. Jhenny Castillo Tapia

Ing. Ronald Yeber Cruz Delgado

Bolivia 2008