5
$\begingroup$

I was requested to draw the graph of a finite state machine whose language is

$$L = \{ w \in \{0, 1\}: w \text{ has $2k$ ones and $3q$ zeros }\}$$

In other words, the number of ones must be even and the number of zeros must be a multiple of $3$.

I have failed in my attempts to draw the graph of a DFA that satisfies this. More generally, though, I do not know an algorithmic procedure (should there be one) to draw a DFA given a language.

How does such DFA look like? More generally, is there a procedure to draw or conceive a DFA given a language?

$\endgroup$

2 Answers 2

7
$\begingroup$

One way to look at these specific problems is to have states labeled $(x,y)$ where $x$ will correspond to the ones seen so far and $y$ similarly to the zeros so far. These are taken mod 2 or mod 3 respectively so, for instance the $y$ value 2 will represent $2,5,8,11,\dots$.

You'll then have six states: $(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)$. For example, if you've seen 7 ones and 5 zeros you'll be in state $(1,2)$ since the remainder of 7 divided by 2 is 1 and the remainder of 5 divided by 3 is 2. From there it should be simple to construct the DFA.

$\endgroup$
2
  • 1
    $\begingroup$ @kkm sure enough. I goofed. As for your accepting state, I didn't want to give the whole thing away. $\endgroup$ Commented May 13, 2023 at 17:37
  • $\begingroup$ “I didn't want to give the whole thing” — I'm deleting my comment then. :) $\endgroup$ Commented May 15, 2023 at 0:01
4
$\begingroup$

There is a general approach, though I am not sure knowing it is of practical use. Fix an alphabet $\Sigma$ and let $L$ be a regular language. Define the following equivalence relation on $\Sigma^*$: $x \sim y$ precisely when for all $z$, $xz \in L$ if and only if $yz \in L$. You can now construct a DFA with states $\Sigma^*/\sim$. The initial state is $\epsilon$, state $[x]$ has an $a$-transition to $[xa]$ for every $a \in \Sigma$, and $[x]$ is an accepting state precisely when $x \in L$.

There are a number of conditions that have to be checked: we are working with equivalence classes, so you need to ensure all this is well-defined. Doing exercises 1.51 and 1.52 from Sipser's Introduction to the Theory of Computation is illustrative here.

That's the general construction. It is not quite an algorithm, since it isn't in general clear how to figure out whether $x \sim y$. It illustrates a key question that you want to ask yourself to draw the DFA, namely "when should two input words $x$ and $y$ lead to the same state?"

For finding a DFA that recognises a particular language like the one in your question, it can help to think about what information the states of the DFA need to capture. For example, here you may start by noting that the number of ones and zeroes in a string $w$ is important, but that their order is not; that means that when $x$ is a permutation of $y$, we will have $x \sim y$.

Try to find other properties that are not important, until you end up with a finite description.

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