Es $L = \{a^{n+2} b^n | n \ge 0\}$ ¿contexto libre o regular?

Question

¿Es la lengua $L = \{ a^{n+2} b^n | n \ge 0 \}$ ¿contexto libre? Si es así, ¿cuál es una gramática libre de contexto para ella? Si es regular, ¿cuál es una gramática lineal correcta para ella?

Answer 1

Pista 1: Modificar la gramática libre de contexto habitual para para $L_1 = \{ a^n b^n : n \geq 0 \}$ para "rellenar el hueco" entre el $a$ s y $b$ s. (Obsérvese que $w \in L$ si $w = a^n aa b^n$ para algunos $n \geq 0$ .)

Pista 2: Recuerde que/por qué $L_1$ , arriba, no es regular. Modifica esta prueba. (Y, para ser honestos, muy poco es necesaria una modificación).