1
$\begingroup$

$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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow thanks I didn't think of that. $\endgroup$ – Matt Apr 3 '13 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.