Una gramática formal es un conjunto de reglas para reescribir cadenas de caracteres, junto con un símbolo inicial desde el cual debe comenzar la reescritura. 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.
Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la jerarquía de Chomsky). Imaginemos una gramática con estas dos reglas:
- A → bA
- A → c
El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son los símbolos terminales. Para generar cadenas de caracteres, la idea es sustituir el símbolo inicial de la izquierda por los símbolos de la derecha, y luego repetir el proceso hasta que sólo haya símbolos terminales. Por ejemplo:
- A → bA → bbA → bbbA → bbbc
Esta gramática da lugar a un lenguaje formal que consiste en el conjunto de todas las cadenas de caracteres que pueden ser generadas por medio ellas. Por ejemplo: bbbc, bbbbbbbbc, c, bc, etc.
Para comprender mejor la idea, podemos considerar un modelo de reescritura para el español:
- O → SUJ PRED (Oración → Sujeto Predicado)
- SUJ → Det N (Sujeto → Determinante Nombre)
- PRED → V COMP (Predicado → Verbo Complemento)
- Det → el
- N → niño, (hombre, anciano)
- V → duerme, (ríe, come)
- COMP → plácidamente, (intranquilo)
Comentarios
Publicar un comentario