Lenguajes Formales Y Automatas

Unidad 6.- Introducción a los Lenguajes formales

Ing. Miguel Ángel Durán Jacobo 1

Lenguaje formal

En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de

palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de

caracteres) finito.

Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, en

derecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla

cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal, en

el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes

mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir

métodos computacionales. Sin embargo, hoy en día, el punto de vista de que la naturaleza

esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido informal

antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes formales (en

el sentido estricto de este artículo) gana cada vez más adeptos.

Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por

ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de

todas las cadenas que contienen el mismo número de símbolos a que b, por ejemplo.

La palabra vacía (esto es, la cadena de longitud cero) es permitida y frecuentemente denotada

mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud

también finita, un lenguaje puede bien incluir un número infinito de palabras.

Algunos ejemplos varios de lenguajes formales:

• el conjunto de todas las palabras sobre {a, b}

• el conjunto {an: n es un número primo}

• el conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de

programación

• el conjunto de entradas para las cuales una particular máquina de Turing se detiene.

Los lenguajes formales pueden ser especificados en una amplia variedad de maneras, como:

• cadenas producidas por una gramática formal (ver Jerarquía de Chomsky)

• cadenas producidas por una expresión regular

• cadenas aceptadas por un autómata, tal como una máquina de Turing.

Varias operaciones pueden ser utilizadas para producir nuevos lenguajes a partir de otros dados.

Supóngase que L1 y L2 son lenguajes sobre un alfabeto común.

Entonces:

• la concatenación L1L2 consiste de todas aquellas palabras de la forma vw donde v es

una palabra de L1 y w es una palabra de L2

• la intersección L1&L2 consiste en todas aquellas palabras que están contenidas tanto

en L1 como en L2

• la unión L1|L2 consiste en todas aquellas palabras que están contenidas ya sea en L1

o en L2

Unidad 6.- Introducción a los Lenguajes formales

Ing. Miguel Ángel Durán Jacobo 2

• el complemento ~L1 consiste en todas aquellas palabras producibles sobre el

alfabeto de L1 que no están ya contenidas en L1

• el cociente L1/L2 consiste de todas aquellas palabras v para las cuales existe una

palabra w en L2 tales que vw se encuentra en L1

• la estrella L1

* consiste de todas aquellas palabras que pueden ser escritas de la

forma W1W2...Wn donde todo Wi se encuentra en L1 y n ≥ 0. (Nótese que esta

definición incluye a & epsilon en cualquier L*)

• la intercalación L1*L1 consiste de todas aquellas palabras que pueden ser escritas de

la forma v1w1v2w2...vnwn son palabras tales que la concatenación v1...vn está en L1, y

la concatenación w1...wn está en L2

Una pregunta que se hace típicamente sobre un determinado lenguaje formal L es cuán difícil es

decidir si incluye o no una determinada palabra v. Este tema es del dominio de la teoría de la

computabilidad y la teoría de la complejidad computacional.

Por contraposición al lenguaje propio de los seres vivos y en especial el lenguaje humano,

considerados lenguajes naturales, se denomina lenguaje formal a los lenguajes «artificiales»

propios de las matemáticas o la informática, los lenguajes artificiales son llamados lenguajes

formales (incluyendo lenguajes de programación). Sin embargo, el lenguaje humano tiene una

característica que no se encuentra en los lenguajes de programación: la diversidad.

En 1956, Noam Chomsky creó la Jerarquía de Chomsky para organizar los distintos tipos de

lenguaje formal.

LENGUAJES

Se considera el conjunto S* que consta de todas las cadenas finitas de elementos del conjunto S.

Existen muchas interpretaciones posibles de los elementos de S* , según la naturaleza de S. Si se

piensa en S como un conjunto de “palabras”, entonces S* se puede considerar como la colección

de todas las “oraciones” posibles formadas con palabras de S. Por supuesto, tales “oraciones” no

necesariamente tienen sentido ni una estructura evidente. Se puede pensar un lenguaje como una

especificación completa, al menos en principio, de tres cosas. En primer lugar, debe existir un

conjunto S con todas las “palabras” que se consideran parte del lenguaje. En segundo lugar, hay

que designar un subconjunto de S” como el conjunto de las “oraciones con construcción

adecuada” en el lenguaje.

Supóngase, a manera de ejemplo, que S consta de todas las palabras del español. La

especificación de una oración con construcción adecuada implica todas las reglas de la gramática

española; el significado de una oración queda determinado por esta construcción y por el

significado de las palabras.

La oración “Iba a la tienda Juan Jorge a cantar”

Es una cadena en S” pero no una oración con una construcción adecuada. La disposición de los

sustantivos y los verbos no es válida.

Unidad 6.- Introducción a los Lenguajes formales

Ing. Miguel Ángel Durán Jacobo 3

Por otro lado, la oración “Los sonidos azules se sientan y cruzan la pierna bajo la cima de la

montaña” tiene una construcción adecuada pero carece completamente de sentido.

Para otro ejemplo, S podría constar de los enteros, los símbolos +, —, X y ÷, así como los

paréntesis izquierdo y derecho. Se obtendrá un lenguaje si se designa como adecuadas las

cadenas en S” que representen sin ambigüedades expresiones algebraicas con paréntesis.

Así, ((3 — 2) + (4 X 7)) ÷ 9 y (7 — (8 — (9 — 10))); son “oraciones” con construcción adecuada

en este lenguaje.

Por otro lado, (2 — 3)) + 4, 4 — 3 — 2 y)2 + (3 —) X 4 no tienen una construcción adecuada. La

primera tiene demasiados paréntesis, la segunda, pocos (no se sabe cuál resta se debe realizar

primero) y la tercera tiene paréntesis y números completamente fuera de lugar.

Todas las expresiones con construcción adecuada tienen sentido, excepto las que implican la

división entre cero.

El significado de una expresión es el número racional que representa. Así, el significado de ((2 —

1) ÷ 3) + (4 X 6) es 73/3, mientras que 2 + (3 ÷ 0) y (4 + 2) — (0÷ 0) no tienen sentido.

La disciplina que regula la construcción adecuada de las oraciones es la sintaxis de un lenguaje.

La que se encarga del significado de las oraciones es la semántica de un lenguaje.

Gramáticas

Una gramática para estructura de expresiones G es una 4-ada ( , , o ,a V S v ), donde V es un

conjunto finito, S es un subconjunto de V v ∈V − S 0 , y aes una relación finita en V * . La idea

es que S es, como ya se ha analizado, el conjunto de todas las “palabras” permitidas en el

lenguaje, y V consta de S además de algunos otros símbolos. El elemento 0 v de V es un punto de

partida para las sustituciones, que serán analizadas en breve. Por último la relación a sobre V*

especifica los reemplazos permisibles, en el sentido de que, si wa w’ se puede reemplazar w

con w’ siempre que aparezca la cadena w, ya sea sola o como subcadena de alguna otra cadena.

Tradicionalmente, a la proposición wa w’ se le llama producción de G. Entonces, w y w’ son

los lados izquierdos y derecho de la producción, respectivamente. Supóngase que ninguna

producción de G tiene a la cadena vacía ∧ como lado izquierdo. Es la a relación de producción

de G.

Esto parecería complicado, pero en realidad es una idea sencilla, como muestran los siguientes

ejemplos.

Si G = ( , , ,a o V S v ) es una gramática para la estructura de oraciones, S es el conjunto de

símbolos terminales y N = V — S es el conjunto de símbolos no termina obsérvese que V = S ∪ N.

Unidad 6.- Introducción a los Lenguajes formales

Ing. Miguel Ángel Durán Jacobo 4

Ejemplo 1. Sea S = {Juan, Julia, maneja, corre, descuidadamente, rápido, frecuentemente),

N = {oración, sujeto, predicado, verbo, adverbio) y sea V=S ∪ N. Sea 0 v =oración, y supóngase

que la relación a en V* queda descrita enumerando todas las producciones como sigue.

Oración a sujeto predicado

Sujeto

...