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