Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?

118 Views Asked by At

Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?

1

There are 1 best solutions below

0
On

Hint 1: Modify the usual context-free grammar for for $L_1 = \{ a^n b^n : n \geq 0 \}$ to "fill in the gap" between the $a$s and $b$s. (Note that $w \in L$ iff $w = a^n aa b^n$ for some $n \geq 0$.)

Hint 2: Recall that/why $L_1$, above, is not regular. Modify this proof. (And, to be honest, very little modification is needed.)