En la teoría del lenguaje formal , una gramática (cuando no se da el contexto, a menudo llamada gramática formal para mayor claridad) describe cómo formar cadenas del alfabeto de un idioma que son válidas de acuerdo con la sintaxis del idioma . Una gramática no describe el significado de las cadenas o lo que se puede hacer con ellas en cualquier contexto, solo su forma. Una gramática formal se define como un conjunto de reglas de producción para tales cadenas en un lenguaje formal.
La teoría del lenguaje formal, la disciplina que estudia las gramáticas y los lenguajes formales, es una rama de las matemáticas aplicadas . Sus aplicaciones se encuentran en informática teórica , lingüística teórica , semántica formal , lógica matemática y otras áreas.
Una gramática formal es un conjunto de reglas para reescribir cadenas, junto con un "símbolo de inicio" a partir del cual comienza la reescritura. Por tanto, se suele pensar en una gramática como un generador de lenguaje. Sin embargo, a veces también se puede utilizar como base para un " reconocedor ", una función en informática que determina si una determinada cadena pertenece al idioma o es gramaticalmente incorrecta. Para describir tales reconocedores, la teoría del lenguaje formal utiliza formalismos separados, conocidos como teoría de autómatas . Uno de los resultados interesantes de la teoría de los autómatas es que no es posible diseñar un reconocedor para ciertos lenguajes formales. [1] Análisises el proceso de reconocer un enunciado (una cadena en los lenguajes naturales) dividiéndolo en un conjunto de símbolos y analizando cada uno contra la gramática del idioma. La mayoría de los lenguajes tienen los significados de sus enunciados estructurados de acuerdo con su sintaxis, una práctica conocida como semántica compositiva . Como resultado, el primer paso para describir el significado de un enunciado en el lenguaje es desglosarlo parte por parte y observar su forma analizada (conocida como su árbol de análisis sintáctico en informática y como su estructura profunda en gramática generativa ).
Pāṇini 's tratado Astadyayi da reglas formales de producción y definiciones para describir la gramática formal de sánscrito . [2] Existen diferentes usos de "forma" y "formalismo", que han cambiado con el tiempo, dependiendo de los campos con los que el autor relevante estuvo en contacto. En [3] se ofrece una descripción histórica del concepto .
Una gramática consiste principalmente en un conjunto de reglas de producción , reescribiendo reglas para transformar cadenas. Cada regla especifica un reemplazo de una cadena en particular (su lado izquierdo ) por otra (su lado derecho ). Se puede aplicar una regla a cada cadena que contiene su lado izquierdo y produce una cadena en la que una ocurrencia de ese lado izquierdo ha sido reemplazada por su lado derecho.
A diferencia de un sistema semi-Thue , que está totalmente definido por estas reglas, una gramática distingue además entre dos tipos de símbolos: símbolos no terminales y terminales ; cada lado izquierdo debe contener al menos un símbolo no terminal. También distingue un símbolo no terminal especial, llamado símbolo de inicio .