Tipos de Lenguaje Formal

Zaraos Vázquez Jorge Alejandro

aleh.kz@hotmail.com

Resumen

En este reporte se introducirá los conceptos

teóricos necesarios sobre la teoría de lenguajes

formales el conjunto finito o infinito de cadenas finitas

de símbolos primitivos formadas por un alfabeto y una

gramática especificada, así como los diferentes tipos

de las jerarquías gramaticales regulares,

recursivamente enumerables, independiente y

dependiente del contexto estos divididos en jerarquías.

1. Cuerpo

1.1. Definiciones previas

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) = {η ϵ VT*/S → η}

Una sentencia pertenece a L(G) si:

-está compuesta de símbolos terminales.

-la sentencia puede derivarse del símbolo inicial S

aplicando las reglas de producción de la gramática. [1]

1.1.1. Propiedad. Dos gramáticas son equivalentes si

ambas generan el mismo lenguaje.

y son equivalentes si L( )= L( )

1.1.2. Alfabeto. Conjunto finito de símbolos, no vacio.

Para definir que un símbolo a pertenece a un alfabeto V

se utiliza notación a ϵ V. Los alfabetos se definen por

enumeración de los símbolos que contienen. Así como

por ejemplo:

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

= {a, b c, d, 0, 1, 2, *, #, +}

= {if, then, end, a, b, =, >} [4]

1.1.3. Gramática. Conjunto finito de reglas para

formar cadenas finitas juntando símbolos del alfabeto,

es una cuádrupla G = (NT, T, S, P). NT = {conjunto finito de símbolos no terminales}

T = {conjunto finito de símbolos terminales}

S = {es el símbolo inicial y pertenece a NT}

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

1.2. Jerarquía de las gramáticas

Es una clasificación jerárquica de distintos tipos

de gramáticas formales que generan lenguajes

formales. Hay 4 distintos tipos de gramáticas en

función de la forma de las derivaciones de P. [2]

1.2.1. Gramática de tipo 0. Llamada también

gramática no restringida o recursivamente enumerable,

es un lenguaje formal para el cual existe una máquina

de Turing que acepta y se detiene con

cualquier cadena del lenguaje, pero que puede parar y

rechazar, o bien iterar indefinidamente, con una cadena

que no pertenece al lenguaje, en contraposición a

los lenguajes recursivos en cuyo caso se requiere que la

máquina de Turing pare en todos los casos. Las reglas

de derivación son de la forma: α → β

Siendo α ϵ (NT ∪ T y β ϵ (NT ∪ T)*, es decir la

única restricción es que no puede haber reglas de la

forma

ƛ → β donde ƛ es la cadena vacía. [6]

Los lenguajes recursivamente enumerables son

cerrados con las siguientes operaciones. Esto es, si L y

P son dos lenguajes recursivamente enumerables,

entonces los siguientes lenguajes son recursivamente

enumerables también: [3]

Cierre estrella L* de L, concatenación LP de L y P,

la unión L ∪ P de L y P, la intersección L ᴖ P de L y P.

1.2.2. Gramática de tipo 1. Llamada gramática

sensible al contexto es equivalente a una máquina de

Turing no determinista linealmente acotada, también

llamado Autómata linealmente acotado. Se trata de

una máquina de Turing no determinista con una cinta

de sólo kn posiciones, donde n es el tamaño de la

entrada y k es la constante asociada a la máquina. Esto

significa que cada lenguaje formal que puede ser

decidido por una máquina es un lenguaje sensible al

contexto en ellas las reglas de producción son de la

forma: αAβ → αγβ

Estas gramáticas tienen reglas de la forma αAβ →

αγβ con A un no terminal y α, β y γ cadenas de

terminales y no terminales. Las cadenas α y β pueden

ser vacías, pero γ no puede serlo. La regla S → ϵ está

permitida si S no aparece en la parte derecha de

ninguna regla. Los lenguajes descritos por estas

gramáticas son exactamente todos aquellos lenguajes

reconocidos por una máquina de Turing determinista

cuya cinta de memoria está acotada por un cierto

número entero de veces sobre la longitud de entrada,

también conocidas como autómatas linealmente

acotados.[3]

Siendo A ϵ NT; α, β ϵ (NT ∪ T)* y γ ϵ (VN ∪ VT .

Estas gramáticas se llaman sensibles al contexto,

pues se pueden reemplazar A por γ siempre que estén

en el contexto α…β.

La unión, intersección, y concatenación de dos

lenguajes sensibles al contexto es un lenguaje sensible

al contexto. El complemento de un lenguaje sensible al

contexto es en sí mismo sensible al contexto.

Cada gramática libre de contexto es un lenguaje

sensible al contexto. Ejemplo: La gramática G = ({a,

b}, {A, S}, S, P) donde P son las producciones

siguientes: [2]

S → aS

S → aA

A → bA

A → b

1.2.3. Gramática de tipo 2. Llamada también de

contexto libre. Sus reglas tan solo admiten tener un

símbolo no terminal en su parte izquierda, es decir son

de la forma: A → α Siendo A ϵ NT y α ϵ (NT ∪ T .

Si cada regla se representa como un par ordenado

(A, α), el conjunto P es un subconjunto del conjunto

cartesiano NT x ({T ∪ NT} . La denominación

contexto libre se debe a que se puede cambiar A por α,

independientemente del contexto que aparezca A. [5]

Las reglas son de la forma A → α con A un no

terminal y α una cadena de terminales y no terminales.

Estos lenguajes son aquellos que pueden ser

reconocidos por un autómata con pila. [1]

El término libre de contexto se refiere al hecho de

que el no terminal A puede siempre ser sustituido por α

sin tener en cuenta el contexto en el que ocurra.

Un lenguaje formal es libre de contexto si hay una

gramática libre de contexto que lo genera.

Una de las definiciones alternativas y equivalentes

de lenguaje libre de contexto emplea autómatas no

deterministas, un lenguaje puede ser también modelado

como un conjunto de todas las secuencias de

terminales aceptadas por la gramática, la unión y

concatenación de dos lenguajes libres de contexto, el

inverso de un lenguaje libre de contexto, los lenguajes

regulares, la intersección de un lenguaje libre de

contexto y un lenguaje regular es libre de contexto, la

intersección no tiene por qué serlo, para demostrar que

un lenguaje dado no es libre de contexto, se puede

emplear el Lema del bombeo para lenguajes libres de

contexto. Ejemplo: La gramática G = ({S, A, B}, {a,

b}, S, P,) cuyas producciones P serán las siguientes:[4]

S → aB A → bAA

S → bA B → b

A → a B → bS

A → aS B → aBB

1.2.4. Gramática de tipo 3. Las gramáticas de tipo 3

también denominadas regulares o gramáticas lineales.

Estas gramáticas se restringen a aquellas reglas que

tienen en la parte izquierda un no terminal, y en la

parte derecha un solo terminal, posiblemente seguido

de un no terminal. La regla S → ϵ también está

permitida si S no aparece en la parte derecha de

ninguna regla. Estos lenguajes son aquellos que pueden

ser aceptados por un autómata finito. También esta

familia de lenguajes pueden ser obtenidas por medio

de expresiones regulares, es decir de la forma:

A → aB

A → a

Donde A, B ϵ NT y α ϵ T. Satisface las siguientes

propiedades, los lenguajes más sencillos que se

considerarán son los lenguajes regulares, es decir, los

que se pueden generar a partir de los lenguajes básicos,

con la aplicación de las operaciones de unión,

concatenación y * de Kleene un número finito de

veces. [5]

Puede ser reconocido por un autómata finito

determinista, un autómata finito no determinista,

un autómata de pila, un autómata finito alterno,

una máquina de Turing de solo lectura. Es generado

por, una gramática regular, una gramática de prefijos.

Es descrito por una expresión regular. [6]

Los lenguajes regulares son cerrados con las

siguientes operaciones, de modo que si L y P son

lenguajes regulares los siguientes lenguajes también

serán regulares: El complemento “L” de L, la clausura

o estrella de Kleene L* de L, el homomorfismo φ(L)

de L, la concatenación L'P de L y P, la

unión L ∪ P de L y P, la intersección L ∩ P de L y P, y

la diferencia L \ P de L y P, el reverso LR de L.

Ejemplo: La gramática G=({a, b}, {A, S}, S, P) donde

P son las producciones que se muestran a continuación.

S → aS

S → aA

S → bA

S → b

1.2.5. Relación de inclusión. Se denomina lenguaje

tipo 0 al generado por una gramática de tipo 0. De la

misma forma, se denomina lenguajes de tipo 1, 2 y 3, a

los generados por las gramáticas de tipo 1, 2 y 3,

respectivamente. [3]

Si los lenguajes generados por los distintos tipos de

gramáticas se relacionan entre sí con respecto a la

relación de inclusión se obtiene: [1]

{L( )} ⊂ {L( )} ⊂ {L( )} ⊂ {L( )}

Figura 1. Relación de inclusión entre los distintos tipos

de gramáticas.

2. Conclusión

Los cuatro tipos de gramáticas estudiados

anteriormente (tipo 0, tipo 1, tipo 2, y tipo 3), cada una

de ellas tiene restricciones más fuertes que las

anteriores. Las gramáticas de tipo 0, contienen a todas

las demás. Las de tipo 1 contienen alas de tipo 2 y tipo

3, y por último las de tipo 2 contienen alas de tipo 3, es

decir, una gramática de tipo 3 es de tipo 2, tipo 1 y 0.

Por lo tanto se define una jerarquía de gramáticas

respecto de la relación de inclusión de ahí el nombre de

jerarquías.

Tomando como referencia un lenguaje formal, la

gramática de tipo 3 que es la que es incluida en cada

tipo es el lenguaje más simple dentro de la jerarquía,

esta se suele expresar en diferentes formas como las

expresiones regulares. Todo lenguaje formal finito

constituye a un regular, las gramáticas regulares sólo

pueden generar a los lenguajes regulares de manera

similar a los autómatas finitos y las expresiones

regulares, son las gramáticas más restrictivas el lado

derecho de una producción debe contener un símbolo

terminal y, como máximo, un símbolo no terminal

Un ejemplo de estas son todas las cadenas sobre el

alfabeto {a, b} que contienen un número par de a o el

lenguaje que consiste en varias a seguidas de varias b.

Referencias [1] Aho A.V. y Ullman J.D., 1973 The Theory of Parsing,

Translation and Com-pilin, Vol. II: Compiling, Prentice-Hall.

[2] Juan Manuel cueva Lovelle, lenguajes gramáticas y

autómatas, Universidad de Oviedo (España), 2 Edición,

Noviembre 2011.

[3] Alfonseca M., Sancho J. y Martínez Orga M., 1987,

Teoría de lenguajes gramáticas y autómatas, Ediciones

Universidad y Cultura.

[4] Chomsky N., 1962, Context-free grammars and

pushdown storage. Quarterly Prog. Rept. No. 65, pp. 187-

194, MIT REs. Lab. Elect., Cambridge, Mass.

[5] Joaquín Aranda, Natividad Duro, José Luis Fernández,

José Jiménez, Fernando Morilla, "Fundamentos de Lógica

Matemática y Computación", Sanz y Torres, 2006.

[6] Sipser, M. (1996), Introduction to the Theory of

Computation, PWS Publishing Co.