patternMinor
Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language
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?
$$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.
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.