top of page

Definicion

Según el Websters New Collegiate Dictionary, lenguaje es un “sistema de palabras y métodos para combinar palabras, usado y comprendido por una comunidad de tamaño considerable”. Estos lenguajes, con frecuencia, se conocen como lenguajes naturales para distinguirlos de los lenguajes formales, que se usan para modelar los lenguajes naturales y comunicarse con las computadoras. Las reglas de un lenguaje natural son muy complejas y su caracterización completa es difícil. Por otro lado, es posible especificar por completo las reglas que sigue la construcción de ciertos lenguajes formales. Comenzaremos con una definición de lenguaje formal.

Sea A un conjunto finito. Un lenguaje (formal) L sobre A es un subconjunto de A*, el conjunto de todas las cadenas sobre A.


Sea A={a, b}. El conjunto Lde todas las cadenas sobre Aque contienen un número impar de símbolos aes un lenguaje sobre A.

Como se vio en el ejemplo 12.2.9, Les precisamente el conjunto de cadenas sobre A aceptadas por el autómata de estado finito de la figura 12.2.7. 


Una manera de definir un lenguaje consiste en dar una lista de las reglas que se supone que el lenguaje debe obedecer.

 

Una gramática de estructura de frases (o simplemente gramática) G consiste en

a) Un conjunto finito N de símbolos no terminales

b) Un conjunto finito T de símbolos terminales donde N∩T=∅

c) Un subconjunto finito P de , llamado conjunto de producciones

d) Un símbolo de inicio σ ∈N.

 

Se escribe G=(N, T, P, σ)

Una producción (A, B) ∈P suele escribirse  

   

La definición 12.3.3 c) establece que en la producción A→B, A ∈(N∪T)* −T* yB ∈ (N ∪ T)*; entonces, A debe incluir al menos un símbolo no terminal, mientras que B puede consistir en cualquier combinación de símbolos no terminales y terminales. 

Ejercicios

Sea

 

N ={ σ, S} T ={ a, b}

P ={ σ →bσ, σ →aS,

S →bS, S →b}.

 

Entonces G=(N, T, P, σ) es un gramática. Dada una gramática G, se puede construir un lenguaje L(G) a partir de G usando las producciones para derivar las cadenas que constituyen L(G). La idea es comenzar con el símbolo de inicio y luego usar las producciones repetidas veces hasta que se obtiene una cadena de símbolos terminales. El lenguaje L(G) es el conjunto de todas estas cadenas obtenidas. La definición 12.3.5 da los detalles formales.

 

Sea G=(N, T, P, σ) una gramática.

Si α→β es una producción y xαy∈(N∪T)*, 6 decimos que xβy se puede derivar directamente de x α y y se escribe

xαy ⇒ xβy.


Si α1 ∈ (N ∪ T)* para i = 1, . . . , n, y αi+1 se deriva directamente de αi para i = 1, . . . , n – 1, se dice que αn se puede derivar de α1 y se escribe

α1 ⇒ αn.

 

Llamamos

 

α1 ⇒ α2 ⇒···⇒αn
 

ala derivación de αn (a partir de α1). Por convención, cualquier elemento de (N∪T)* se puede derivar de sí mismo.

 

El lenguaje generado por G, escrito L(G), consiste en todas las cadenas sobre T que se pueden derivar de σ.

Gramatica de los enteros

Una gramática para enteros Un entero se define como una cadena consistente en un signo opcional (+o −) seguido de una cadena de dígitos (0 al 9). La siguiente gramática genera todos los enteros.

 

 

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

< entero > ::= < entero con signo >|< entero sin signo >

< entero con signo > ::=+< entero sin signo >|− < entero sin signo >

< entero sin signo > ::= < dígito >|< dígito ><entero sin signo > 

 

El símbolo de inicio es < entero >. Por ejemplo, la derivación del entero –901 es
< entero > ⇒ < dígito con signo > 

⇒− < entero sin signo >

⇒− < dígito ><entero sin signo > 

⇒− < dígito ><dígito ><entero sin signo > 

⇒− < dígito ><dígito ><dígito > 

⇒−9 < dígito ><dígito > 

⇒−90 < dígito > 

⇒−901. 

 

 

En la notación de la definición 12.3.3, este lenguaje consiste en

1. El conjunto N={< dígito >, < entero >, < entero con signo>, < entero sin signo >} de símbolos no terminales

2. El conjunto T={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −} de símbolos terminales

3. Las producciones
 

< dígito > →0, . . . , < dígito > →9 

< entero > → < entero con signo > 

< entero > → < entero sin signo >

< entero con signo > →+< entero sin signo > 

< entero con signo > →−< entero sin signo > 

< entero sin signo > → < dígito > 

< entero sin signo > → < dígito ><entero sin signo > 

 

4. El símbolo de inicio < entero>.

Es típico que los lenguajes de computadora, como FORTRAN, Pascal y C++se espe-cifiquen en BNF.

 

Sea G una gramática y sea λ la cadena nula.

a) Si cada producción es de la forma

 

αAβ → αδβ, where α, β ∈(N ∪T)∗, A ∈ N,

δ ∈(N ∪T)∗−{λ},

 

G recibe el nombre de gramática sensible al contexto (o tipo 1).

 

b) Si cada producción es de la forma
A → δ, where A ∈ N, δ ∈(N ∪T)∗,


G recibe el nombre de gramática libre de contexto (o tipo 2).

 

c) Si cada producción es de la forma

A →a or A →aBor A → λ, where A, B ∈ N, a ∈ T,
G recibe el nombre de gramática regular (o tipo 3).
De acuerdo con la forma (12.3.1), en una gramática sensible al contexto, se puede sustituir A por δ si A está en el contexto de α y β. En una gramática libre de contexto, (12.3.2) establece que se puede sustituir A por δ en cualquier momento. Una gramática regular tiene reglas de sustitución especialmente sencillas: se sustituye un símbolo no terminal por un símbolo terminal, por un símbolo terminal seguido de un símbolo no terminal, o por la cadena nula.

Observe que una gramática regular es una gramática libre de contexto y que una gramática libre de contexto sin producciones de la forma A→ λ es una gramática sensible al contexto.

Algunas definiciones permiten sustituir a por una cadena de terminales en la definición 12.3.8c); sin embargo, se puede demostrar (vea el ejercicio 32) que las dos definiciones producen los mismos lenguajes.

 

 

 

 

 

 

 

La gramatica definida por

T ={ a, b, c}, N ={ σ, A, B, C, D, E},

con producciones


σ →aAB,  σ →aB,  A →aAC,  A →aC,  B → Dc,  D →b,  CD→CE,  CE→ DE,  DE→ DC,  Cc→ Dcc

 

 

y símbolo de inicio σ, es sensible al contexto. Por ejemplo, la producción CE → DE dice que se puede sustituir C por D si C va seguido de E, y la producción Cc → Dcc dice que se puede sustituir C por Dc si C va seguido de c. Se puede derivar DC a partir de CD, ya que

 

CD⇒CE⇒ DE⇒ DC.

 

La cadena a3b3c3 está en L(G), ya que se tiene

 

σ ⇒ aAB⇒aaACB ⇒aaaCCDc⇒aaaDCCc⇒aaaDCDcc ⇒ aaaDDCcc⇒aaaDDDccc⇒aaabbbccc.

 

Se puede demostrar

 

L(G) ={ anbncn |n =1, 2, ...}.

 


Es natural permitir que el lenguaje L(G) herede una propiedad de una gramática G. La siguiente definición precisa este concepto.

Un lenguaje L es sensible al contexto (respectivamente, libre de contexto, regular) si existe una gramática sensible al contexto (respectivamente, libre de contexto, regular) G con L =L(G)

Automatas, Gramaticas y lenguaje

Se cierra esta sección con una introducción breve de otro tipo de gramáticas que resultan útiles para generar curvas fractales.
 

 

Una gramática de Lindenmayer interactiva libre de contexto consiste en

 

a) Un conjunto finito N de símbolos no terminales

b) Un conjunto finito T de símbolos terminales, donde N ∩T=∅

c) Un conjunto finito P de las producciones A→B, donde A∈N∪T y B∈(N∪T)*

d) Un símbolo de inicio σ ∈N. 

 

La diferencia entre una gramática de Lindenmayer interactiva libre de contexto y una gramática libre de contexto es que la primera permite producciones de la forma A → B, donde A es una terminal o no terminal. (En una gramática libre de contexto, A debe ser una no terminal).

 

Las reglas para derivar las cadenas en una gramática de Lindenmayer interactiva libre de contexto son diferentes de las reglas para derivar cadenas en una gramática de estructura de frases (vea la definición 12.3.5). En una gramática de Lindenmayer interactiva libre de contexto, para derivar la cadena β de todas las cadenas α, todos los símbolos en α debe sustituirse simultáneamente. La definición formal es la siguiente.
 

 

Sea G=(N, T, P, σ) una gramática de Lindenmayer interactiva libre de contexto. Si
 

α = x1···xn

 

y hay producciones
 

xi → βi
 

en P, para i=1, . . . , n, se escribe

 

α ⇒ β1···βn
 

y se dice que β1 · · · βn se puede derivar directamente de α. Si αi+1 se puede derivar de αi para i=1, . . . , n – 1, se dice que αn se puede derivar de α1 y se escribe
 

α1 ⇒ αn.
 

Las implicaciones


α1 ⇒ α2 ⇒···⇒αn
 

se llaman derivación de αn (a partir de α1). Los lenguajes generados por G, escrito L(G), consisten en todas las cadenas sobre T que se pueden derivar de σ.
 

Ejemplo

Copo de nieve de von Koch 

 

Sea 

 

N ={D}

T ={ d,+,−}

P ={D → D− D++D− D, D →d,+→+ ,−→−} .

 

Se interpreta G(N, T, P, D) como una gramática de Lindenmayer libre de contexto. Como un ejemplo de una derivación a partir de D se tiene

 

D ⇒ D− D++D− D ⇒d −d++d −d.
 

Entonces  d-d++d-d-∈ L(G). Ahora se impone un significado para las cadenas en L(G). El símbolo d se interpreta como un comando para dibujar una línea recta de longitud fija en la dirección actual; el signo +se interpreta como un comando para girar a la derecha 60°; el signo −se interpreta como un comando para girar a la izquierda 60°. Si comenzamos a la izquierda y el primer movimiento es horizontal a la derecha, cuando la cadena d−d++d−d se interpreta, se obtiene la curva mostrada en la figura 12.3.1a).

 

 

 

 

 

 

 

 

 

bottom of page