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

Improve this question
$\endgroup$
10
  • 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
    Commented Apr 11, 2015 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
    Commented Apr 11, 2015 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
    Commented Apr 11, 2015 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
    Commented Apr 13, 2015 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
    Commented Apr 14, 2015 at 10:13

1 Answer 1

Reset to default
3
$\begingroup$

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

DFA

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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