Gramática formal
Las gramáticas formales aparecen en varios contextos diferentes: la lógica matemática, las ciencias de la computación y la lingüística teórica, frecuentemente con métodos e intereses divergentes.
Sus aplicaciones se encuentran en la ciencia computacional teórica, la lingüística, la semántica formal, la lógica matemática y otras áreas.
Por lo tanto, una gramática formal generalmente se piensa como una generadora de lenguajes.
Sin embargo, a veces también puede ser usada como la base para un "reconocedor": una función que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.
Por ejemplo: bbbc, bbbbbbbbc, c, bc, etc. Para comprender mejor la idea, podemos considerar un modelo de reescritura para el español: Estas reglas pueden utilizarse para generar la frase "el niño duerme plácidamente", así: Vemos que existen unas definiciones especiales como ORACIÓN, SUJETO, etc. que no aparecen en la frase final formada.
Son unas entidades abstractas denominadas "categorías sintácticas" que no son utilizables en una oración (tienen un papel similar al de las categorías gramaticales de las lenguas naturales).
E igualmente el mismo sistema permite derivar otras oraciones similares usando formas las formas léxicas entre paréntesis: Las categorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases.
La categoría superior sería la FRASE que representa una oración válida en lengua castellana.
Aplicando las jerarquías y sustituyendo elementos, llegamos al punto en donde todas las categorías sintácticas se han convertido en palabras, obteniendo por tanto una oración válida; como por ejemplo: El niño corre.
Además los modelos de lengua natural basados en ellas parecen tener una complejidad polinómica o exponencial, lo cual no parece avenirse con la velocidad con que los hablantes procesan las lenguas naturales.
En cambio las A-gramáticas en general tienen complejidad lineal, simetría entre hablantes y oyentes, sin embargo, ignoran los constituyentes clásicos del análisis sintáctico.
Las formas léxicas y secuencias formadas a partir de ellas están etiquetadas con categorías que indican el tipo de entidad formada y sus posibilidades combinatorias (por ejemplo en una lengua nominal una secuencia de palabras puede constituir un sintagma nominal lo cual especifica con qué otro tipo de categorías puede combinarse este sintagma para formar otro sintagma mayor).
Las gramáticas categoriales se pueden definir como una estructura formal algebraica.
una gramática, y sean α, β, δ, φ, ρ, ... palabras de
Estos dos tipos son mucho menos generales que las gramáticas no restringidas de Tipo 0 (es decir, que pueden ser procesadas o reconocidas mediante máquinas de Turing).
[1] Por ejemplo, todas las lenguas regulares pueden ser reconocidas por un autómata finito.
Para subconjuntos de gramáticas libres de contexto, existen algoritmos para generar analizadores sintácticos LL y analizadores sintácticos LR eficientes, que permiten reconocer los correspondientes lenguajes generados por esas gramáticas.
Las ES-gramáticas como la usada en los primeros modelos de gramática generativa requieren ciertas restricciones para ser computacionalmente tratables.
Para entender esa restricción debe considerarse la interacción entre un hablante y un oyente, el primero genera una oración o secuencia de acuerdo con las reglas de la gramática, el segundo para entender dicha secuencia debe analizar la secuencia para entenderla, encontrando los elementos formantes, interpretándolos y reconstruyendo la relación hay entre ellos (estructura interna).
Para que eso segundo sea posible se requiere que la estructura interna tenga una estructura suficientemente simple como poder analizar sintácticamente las secuencias con un bajo grado de ambigüedad.
El conjunto de fórmulas bien formadas constituyen el vocabulario o léxico, mientras el par
