1
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ Try to use the product construction. $\endgroup$ – Yuval Filmus Oct 18 '18 at 7:15
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ should be "intersection", in places of "product" $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 7:25
  • $\begingroup$ No, I did mean product. $\endgroup$ – Yuval Filmus Oct 18 '18 at 7:28
  • $\begingroup$ ok, just that it is a little more categorical than necessary for an elementary question. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 7:30
0
$\begingroup$

You obviously need six states: Three states for the number of a's modulo 3, and for each of the three states whether a c was received or not.

Let's call these states a0, a1, a2, a0c, a1c, a2c. You obviously start in state a0. Getting a c leaves you in state a0c, a1c or a2c, or moves you from state a0, a1, a2 to a0c, a1c, a2c. Getting an a will move you from a0 -> a1 -> a2 -> a0 or a0c -> a1c -> a2c -> a0c.

a1c and a2c are success states.

$\endgroup$

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.