`` `` ``
S -> asb | ε
`` `` ``
Explicación:
* s: Este es el símbolo de inicio de la gramática. Representa una cadena que pertenece al lenguaje `aⁿbⁿ`.
* a: Representa el personaje literal 'A'.
* b: Representa el carácter literal 'B'.
* |: Representa "o". Indica que hay múltiples reglas de producción para el símbolo de la izquierda.
* ε: Representa la cadena vacía.
Cómo funciona:
1. `s -> asb`: Esta regla genera un 'A', seguido de un 'S' (que eventualmente generará más 'A y' B), seguido de una 'B'. Cada vez que se aplica esta regla, agrega efectivamente una 'A' a la izquierda y una 'B' a la derecha, manteniendo el equilibrio requerido por el idioma.
2. `s -> ε`: Esta regla proporciona el caso base para la recursión. Permite que la derivación termine, produciendo la cadena vacía (donde n =0).
Ejemplos de derivación:
* n =0:cadena vacía (ε)
`S -> ε`
* n =1:"AB"
`S -> asb`
`S -> aεb`
`S -> ab`
* n =2:"aabb"
`S -> asb`
`S -> aasbb`
`S -> aaεbb`
`S -> aabb`
* n =3:"aaabbb"
`S -> asb`
`S -> aasbb`
`S -> aaasbbb`
`S -> aaaεbbb`
`S -> aaabbb`
Por qué este CFG genera solo AⁿBⁿ:
La única forma de derivar una cadena de 'S' es aplicando repetidamente la regla `s -> asb` cero o más veces, seguido de la aplicación de la regla` s -> ε` una vez. Cada aplicación de `s -> asb` agrega una 'A' a la izquierda y otra 'B' a la derecha. Por lo tanto, la cadena resultante siempre tendrá un número igual de 'A y' B's, con todos los 'A que preceden a todas las' B. Esto describe con precisión el lenguaje `aⁿbⁿ`.
Conceptos clave:
* Gramática sin contexto (CFG): Una gramática formal donde las reglas de producción tienen un solo símbolo no terminal en el lado izquierdo y cualquier combinación de símbolos terminales y no terminales en el lado derecho. La aplicación de una regla de producción no depende del contexto en el que aparezca el símbolo no terminal.
* Símbolos de terminal: Símbolos que aparecen en la cadena final (por ejemplo, 'a', 'b').
* símbolos no terminales: Símbolos que representan categorías gramaticales o pasos intermedios en la derivación (por ejemplo, 's').
* Símbolo de inicio: El símbolo no terminal del que se derivan todas las cadenas en el idioma (por ejemplo, 's').
* Reglas de producción: Las reglas que especifican cómo los símbolos no terminales pueden ser reemplazados por otros símbolos (por ejemplo, `s -> asb`).
Este CFG es un ejemplo clásico que a menudo se usa para ilustrar el poder de los CFG y su capacidad para expresar idiomas que no son regulares. El lenguaje `aⁿbⁿ` es un ejemplo estándar de un lenguaje libre de contexto que no es un lenguaje regular.