1.3. Lenguajes, tipos y herramientas

Lenguajes, tipos y herramientas

Lenguaje: Subconjunto del universo del discurso. Conjunto de palabras de un determinado alfabeto. "El alfabeto Σ es también un lenguaje sobre Σ."

Lenguaje vació: Es aquel que no contiene la cadena vacía ni ninguna otra cadena.

    Cardinal ( { Ø } ) = 0

    Cardinal ( { λ } ) = 1

Clausula (cierre) positiva de un lenguaje: El lenguaje obtenido uniendo el lenguaje L con todas sus potencias posibles, excepto L0. Obviamente, ninguna clausura positiva contiene la palabra vacía, a menos que dicha palabra esté en L. Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que:

L+ = L1 U L2 U L3....

W(∑) = Lenguaje universal de ∑.

∑+ = W(∑) - { λ }

Estrella de kleene: Es la unión de todas las potencias de un lenguaje incluso L0. Obviamente, todas las clausuras contienen la palabra vacía. Son evidentes las siguientes identidades:

L0 = λ

L* = L+ U { λ }

L* =L0 U L1 U L2 U L3.....

Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que

∑* = W(∑)

A partir de este momento, representaremos al lenguaje universal sobre el alfabeto Σ con el símbolo Σ*.

 

Tipos de lenguajes:

Natural: Los que hablamos los seres humanos.

Artificial: Los lenguajes de programación de computadoras.

Primera generación: Lenguaje máquina. Los programas se escriben en código binario

Segunda generación: Lenguajes simbólicos. Cada instrucción de la maquina se representan mediante símbolos

Tercera generación: Lenguajes de alto nivel. Una sola instrucción de este tipo representa usualmente varias instrucciones de la máquina.

 

Clasificación de los lenguajes

Chomsky definió cuatro tipos distintos de gramáticas en función de la forma de las reglas de derivación. 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áticas engloba a todos los tipos siguientes.

 

Gramáticas de tipo 0

También llamadas gramáticas no restringidas o gramáticas con estructura de frase. Las reglas de derivación son de la forma:

∝ → β

Siendo ∝ ε (VN U VT)+ y β ε (VN U VT)*, es decir la única restricción es que no puede haber reglas de la forma λ → β donde λ es la cadena vacía.

 

Gramáticas de tipo 1

También llamadas gramáticas sensibles al contexto (en ingles context sensitive). En ellas las reglas de producción son de la forma:

∝ A β → ∝ ɤ β

Siendo A ϵ VN; ∝, β ϵ (VN U VT)* y ɤ ϵ (VN U VT)+

Estas gramáticas se llaman sensibles al contexto, pues se puede reemplazar A por ɤ siempre que estén en el contexto ∝ ... β.

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

S → aB

S → bA

A → a

A → aS

A → bAA

B → b

B → bS

B → aBB

 

Gramática de tipo 2

Las gramáticas de tipo 2 también se denominan gramáticas de contexto libre o libres de contexto (en inglés context free). Sus reglas de producción tan solo admiten tener un símbolo no terminal en su parte izquierda, es decir son de la forma:

A → ∝

Siendo A ϵ VN y ∝ ϵ (VN U VT)+.

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

P ⊂ { N x ( { VN } U { VT } ) + }

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

 

Gramáticas de tipo 3

Las gramáticas de tipo 3 también denominadas regulares o gramáticas lineales 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 ∝ ϵ VT.

 

Gramática

Es un ente formal para especificar de una manera finita al conjunto de cadenas que constituye un lenguaje. "Una gramática es una cuádrupla." (Cueva Lovelle, 2001).

    G = ( VT, VN, S, P )

 

Donde

    VT = { conjunto finito de símbolos terminales }

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

    S es el simbolo inicial y pertenece a VN

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

 

Vocabulario terminal: Se define por enumeración de los símbolos terminales. Todas las cadenas del lenguaje definidos por la gramática están formados con símbolos del vocabulario VT. (Cueva Lovelle, 2001, 7).

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. El vocabulario no terminal se define por enumeración de los símbolos no terminales." (Cueva Lovelle, 2001, 7).

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 ocaciones 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 - { λ }

    V* = V + { λ }

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 distintas cadenas del lenguaje." (Cueva Lovelle, 2001, 7).

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 enumeracion de las distintas producciones, en forma de reglas o por medio de un metalenguaje por ejemplo BNF (Backus Naur Form) o EBNF (Extended Backus Naur Fourm)."

 

Cadena válida: Es aquella cadena que cumple con la gramática establecida.

 

Derivación: "La  derivación  consiste  en  tratar  a  cada  producción  como  una  regla  de  sustitución,  donde  el  símbolo  no  terminal  de  la  cabecera  de  una  regla  se  sustituye  por  la  cadena  formada  por  el  cuerpo de la producción. El árbol sintáctico se construye a partir de las derivaciones."