Gramáticas Independientes del Contexto

Ejercicio 1

Lenguaje y sus palabras

a^2k = (aa)^k

Palabra mínima = aabc

Otras palabras:

• aaaabcc
• aaaaaabccc
• aaaaaaaabcccc

Gramática

En la primer producción nos aseguramos la cadena mínima

1. S → aabc | aaAc
2. A → aaAc | b

Otra gramática equivalente

1. S → aabc | aaAc
2. A → aaAc | B
3. B → b

Derivación

Derivación vertical de la cadena aaaabcc