3
$\begingroup$

I know how to draw a DFA, but I have problems with this specific one:

${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$

This language is regular and there has to exist a DFA (It would be great if someone could leave a comment WHY a language like this one is regular). Finally, I got a solution, but I'm not really satisfied with my solution. How can I present the DFA in a more clearly way? (is it possible to draw a "Planar graph" of it?)

DFA

$\endgroup$
  • 1
    $\begingroup$ Since there are a finite number of equivalence classes for each $|w|_x$ mod 7, maybe trying making these the states. $\endgroup$ – Louis Apr 11 '15 at 10:04
  • 2
    $\begingroup$ @jannnik The whole thing is mod 7, so there's 7 equivalence classes on both side (0,...,6), the fact that the right hand side is an equation doesn't change this. What the equation does is affect which equivalence class you move to when you see a $b$ or $c$ in a slightly more complex way that with the $a$s. $\endgroup$ – Luke Mathieson Apr 11 '15 at 10:20
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 11 '15 at 12:22
  • 2
    $\begingroup$ Make your life easy first: put 0 on one side of the equation, and all the rest on the other side. Then you can work with 5 states, which is a lot more comfortable. Somtimes you can save a lot of energy by thinling a bit first about the way you should transform the problem. $\endgroup$ – babou Apr 13 '15 at 23:26
  • 2
    $\begingroup$ Thanks for your answers. Finally I have a much simpler DFA with 5 states. I put 0 on the left side of the equation, this was a really good idea. The DFA looks a bit like a K5 graph with double edges on the circle (one edge direction for the a's and one for the b's) and the crossing edges in the center of the circle for the c's. $\endgroup$ – jannnik Apr 14 '15 at 10:13
3
$\begingroup$

Here is the minimal DFA. It keeps track of $|w|_a-|w|_b+2|w|_c\bmod 5$.

DFA

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