Lenguaje formal

Lenguaje formal
Esta imagen muestra la relación entre las cadenas de caracteres, las fórmulas bien formadas y los teoremas. En algunos sistemas formales, sin embargo, el conjunto de los teoremas coincide con el de las fórmulas bien formadas.

En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados.[1] [2] Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.

Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.

Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial con los lenguajes naturales.

En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante \epsilon \,, e\, o \lambda \,.

Contenido

Ejemplos de lenguajes formales

  • Un 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 todas las fórmulas bien formadas en la lógica de primer orden.

Especificación de lenguajes formales

Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por ejemplo:

Las cadenas estan formadas por un conjunto de simbolos que pertenecen a un mismo lenguaje, existen dos formas de componer una sentencia o funcion con los simbolos:

Operaciones

Se pueden utilizar varias operaciones 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
  • 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 ε en cualquier L*)
  • La intercalación L1*L2 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.

Verdades concernientes a los lenguajes formales

Teorema 1
El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.
Lema 1
El conjunto de lenguajes en un alfabeto no vacío dado es incontable.
Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto \{a\}\, es incontable. Como sabemos, un lenguaje L en \{a\}\, es un subconjunto de \{a\}^*\,, esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en \{a\}\, es justamente 2^{\{a\}^*}\, (el conjunto de todos los subconjuntos o conjunto potencia de \{a\}^*\,) y es evidente que \{a\}^*\, es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un conjunto infinito de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado.
Demostración del Teorema 1
Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable.
Teorema 2
Los lenguajes son conjuntos contables.
Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado.
Teorema 3
El conjunto de lenguajes formales es contable.
Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio \{0, 1\}^*\,, esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de \{0, 1\}^*\,) y como \{0, 1\}^*\, es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida.

Véase también

Notas y referencias

  1. Mellema, Gregory, «formal language» (en inglés), The Oxford Companion to Philosophy, Oxford University Press, http://www.oxfordreference.com/views/ENTRY.html?subview=Main&entry=t116.e929, consultado el 13 de octubre de 2009 
  2. Shapiro, Stewart, «Classical Logic», en Edward N. Zalta (en inglés), Stanford Encyclopedia of Philosophy (Winter 2009 Edition), http://plato.stanford.edu/archives/win2009/entries/logic-classical/, «Again, a formal language is a recursively defined set of strings on a fixed alphabet.» 

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • 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… …   Enciclopedia Universal

  • Lenguaje Z — Lenguaje Z. El Lenguaje Z es un lenguaje formal utilizado en Ingeniería del software para la especificación formal de un sistema de cómputo, como una fase previa al desarrollo del código de programa para el mismo en un lenguaje de programación.… …   Wikipedia Español

  • formal — adjetivo 1. De la forma: requisito formal, análisis formal. 2. Que cumple con su palabra, obligaciones o compromisos: Es un hombre formal, de palabra, puedes confiar en él. Es un muchacho formal, serio y responsable. Es una empresa formal, no… …   Diccionario Salamanca de la Lengua Española

  • Lenguaje honorífico japonés — El idioma japonés posee numerosas expresiones de respeto o también denominado lenguaje honorífico, que está formado por elementos del lenguaje que permiten mostrar respeto, y cuyo uso es obligatorio en numerosas circunstancias sociales. Las… …   Wikipedia Español

  • Lenguaje de especificación — En el contexto de la ingeniería eléctrica, la computación y ramas afines, un lenguaje de especificación o lenguaje de descripción es un lenguaje formal o semi formal cuya función es construir modelos de los sistemas que se desea elaborar. A… …   Wikipedia Español

  • Lenguaje formalizado — El lenguaje formalizado es un lenguaje sometido a unas «reglas fijas de formación de expresiones y significados». Es una de las características esenciales del lenguaje científico. Incluso hay autores que llegan a opinar que la ciencia en sí misma …   Wikipedia Español

  • Lenguaje de programación — Captura de la microcomputadora Commodore PET 32 mostrando un programa en el lenguaje de programación BASIC, bajo el emulador VICE en una distribución GNU/Linux. Un lenguaje de programación es un idioma artificial diseñado para expresar… …   Wikipedia Español

  • Lenguaje regular — Un lenguaje regular es un tipo de lenguaje formal que 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 …   Wikipedia Español

  • Lenguaje sensible al contexto — En las ciencias de la computación, un lenguaje sensible al contexto es un [[lenguaje formal] que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática… …   Wikipedia Español

  • Lenguaje regular — Un lenguaje regular puede ser reconocido por: ● Un autómata finito ● Una expresión regular ● Una gramática regular Todo lenguaje formal finito constituye un lenguaje regular. Un lenguaje formal infinito puede ser regular o no regular. El lenguaje …   Enciclopedia Universal

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”