Inteligencia Artificial

Lenguaje formal
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.[] 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 formadade 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 unnú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 algunoslenguajes 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 [pic], [pic]o [pic].
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ónde lenguajes formales
Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por ejemplo:
• Cadenas producidas por una gramática formal (véase la jerarquía de Chomsky).
• Cadenas producidas por una expresión regular.
• Cadenas aceptadas por un autómata, tal como una máquina de Turing.
Las cadenas están formadas por un conjunto de símbolos quepertenecen a un mismo lenguaje, existen dos formas de componer una sentencia o función con los símbolos:
• Sintaxis
• Semántica
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 esuna 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 cocienteL1/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 puedenser 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...