patternMinor
Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively?
Viewed 0 times
dfanumbertherespectivelyarestateswhereminimumnumbersdivisible
Problem
While studying automata theory a typical problem that I face is of the following type:
Constructing a DFA with minimum number of states for all strings over
$\{a,b\}$ which have number of $a$’s divisible by $X$ and number of $b$’s
divisible by $Y$ (where $X$ and $Y$ are some positive integer values).
Is there some standard way of solving such problems?
I looked it up over the net and most people seem to have an idea that minimum number of states will be $X \cdot Y$. I don't think that is right. I constructed a DFA with 15 states for $X = 6$ and $Y = 8$.
Also along a similar line suppose the problem is changed slightly and we are
given "number of $a$'s mod $X$ = $P$ and number of $b$'s mod $Y$ = $Q$".
I believe this type of problem will also have a similar solution as the above problem. Only difference will be in the final states of the two machines. Can someone please confirm whether I am right about this?
Constructing a DFA with minimum number of states for all strings over
$\{a,b\}$ which have number of $a$’s divisible by $X$ and number of $b$’s
divisible by $Y$ (where $X$ and $Y$ are some positive integer values).
Is there some standard way of solving such problems?
I looked it up over the net and most people seem to have an idea that minimum number of states will be $X \cdot Y$. I don't think that is right. I constructed a DFA with 15 states for $X = 6$ and $Y = 8$.
Also along a similar line suppose the problem is changed slightly and we are
given "number of $a$'s mod $X$ = $P$ and number of $b$'s mod $Y$ = $Q$".
I believe this type of problem will also have a similar solution as the above problem. Only difference will be in the final states of the two machines. Can someone please confirm whether I am right about this?
Solution
I think the minimum number of states is $X\cdot Y$. In particular, for $X=6$ and $Y=8$, I think 48 states are required.
One can prove this using Myhill-Nerode. The equivalence class (in Myhill-Nerode) of string $s$ is uniquely determined by the pair $\langle n_a(s) \bmod X, n_b(s) \bmod Y \rangle$, where $n_a(s)$ counts the number of $a$'s in $s$, and $n_b(s)$ the number of $b$'s. Two different equivalence classes $\langle i,j \rangle$, $\langle i',j' \rangle$ can be separated by the suffix $a^{X-i} b^{Y-j}$, since that'll take the former to an accepting state and the latter to a non-accepting state (if $i \ne i'$ or $j \ne j'$). This gives us $X \cdot Y$ different equivalence classes, so any DFA accepting this language must have at least $X \cdot Y$ states.
Are you sure you can do it in 15 states, for $X=6$ and $Y=8$? Is it possible you might have made a mistake somewhere in your DFA?
One can prove this using Myhill-Nerode. The equivalence class (in Myhill-Nerode) of string $s$ is uniquely determined by the pair $\langle n_a(s) \bmod X, n_b(s) \bmod Y \rangle$, where $n_a(s)$ counts the number of $a$'s in $s$, and $n_b(s)$ the number of $b$'s. Two different equivalence classes $\langle i,j \rangle$, $\langle i',j' \rangle$ can be separated by the suffix $a^{X-i} b^{Y-j}$, since that'll take the former to an accepting state and the latter to a non-accepting state (if $i \ne i'$ or $j \ne j'$). This gives us $X \cdot Y$ different equivalence classes, so any DFA accepting this language must have at least $X \cdot Y$ states.
Are you sure you can do it in 15 states, for $X=6$ and $Y=8$? Is it possible you might have made a mistake somewhere in your DFA?
Context
StackExchange Computer Science Q#21802, answer score: 6
Revisions (0)
No revisions yet.