# Decidability Turing Machine Problem

$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains at least one string $w$ such that the number of $a$'s in $w$ is a multiple of $5\}$

Show that L is decidable by giving a high level description of a turing machine.

I understand the proof of how to do this given a CFG and string w and deciding whether w is a part of the CFG using a TM, but I'm not entirely sure how to approach the extra constraint.

Thanks for any help.

Outline. Possibly not the smoothest solution, but one way to go about this to note that the language $$L_{\mathtt{5a}} = \{ w \in \{ \mathtt{a} , \mathtt{b} \}^* : \text{the number of }\mathtt{a}\text{s in }w\text{ is a multiple of }5 \}$$ is regular, and that the intersection of a regular language and a context-free language is context-free. (Since a DFA uses no storage memory you can run a DFA and a PDA "in parallel".) An algorithm would then be to construct a CFG/PDA for $L_{\mathtt{5a}} \cap L(G)$ and then check whether the language of this CFG/PDA is nonempty.