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 lo 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 informática que determina si una cadena dada 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 autómatas es que no es posible diseñar un reconocedor para ciertos lenguajes formales. [1] Análisises el proceso de reconocer una expresión (una cadena en lenguajes naturales) dividiéndola en un conjunto de símbolos y analizando cada uno contra la gramática del lenguaje. La mayoría de los idiomas tienen los significados de sus expresiones estructurados de acuerdo con su sintaxis, una práctica conocida como semántica composicional . Como resultado, el primer paso para describir el significado de un enunciado en el lenguaje es dividirlo 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 ).
El tratadoAstadyayi de Pāṇini da reglas de producción formales y definiciones para describir la gramática formal delsánscrito. [2] Hay diferentes usos de "forma" y "formalismo", que han cambiado con el tiempo, dependiendo de los campos con los que estuvo en contacto el autor en cuestión. Una descripción histórica del concepto se da en [3]
Una gramática consiste principalmente en un conjunto de reglas de producción , reescribiendo reglas para transformar cadenas. Cada regla especifica el reemplazo de una cadena en particular (su lado izquierdo ) con 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á completamente 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 .