Decidability of a context free Grammar

Question

Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a.

Is redness decidable? or Semi decidable? will the algorithm go into an infinite loop when presented with certain invalid statements?

Also what about extreme redness?

Answer 1

"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with a is also finite. So you only need to try every string in that finite set.

"Extreme redness" is very different. Here, the question is whether {a}·?* ? L. This is not decidable, even though {a}·?* is a regular language. The simplest proof is to start with the well-known fact that it is not decidable whether a context-free grammar recognises every string in ?*, and derive a contradiction.