# DFA for words with $a$s not a multiple of 3 and at least one $c$

Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$.

Here is an automaton for the first part of language, but I do not know how to devise and attach the second part of the condition $$\#c(w) > 0$$. Because $$C$$ can come in any state.

• Try to use the product construction. – Yuval Filmus Oct 18 '18 at 7:15

The product construction is a way of taking two DFAs for languages $$L_1,L_2$$, and constructing a new DFA for the language $$L_1 \cup L_2$$ or $$L_1 \cap L_2$$. In your case, $$L_1$$ consists of all words in which the number of $$a$$s is not a multiple of 3, and $$L_2$$ consists of all words containing at least one $$c$$. You have already constructed a DFA for $$L_1$$. Construct one for $$L_2$$, and use the product construction to construct one for $$L_1 \cap L_2$$.