HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
zerosfinitecreatingandgenerallanguagefordeterministiconesstrings

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#160134, answer score: 7

Revisions (0)

No revisions yet.