retagged by
492 views
3 votes
3 votes
Let L be the set of strings on $\Sigma = (0,1)$ such that $z$ belongs to $L$ if number of $0$' s in $z$ is divisible by $k. \ k \geq 2$ and number of $1$' s in $z$ is odd. The number of states in the minimal DFA which accept the language $L$ is ______.
retagged by

1 Answer

Best answer
8 votes
8 votes

z belongs to L iff number of 0's in z is divisible by k, k ≥ 2 and number of 1's in z is odd.

For simplicity let K = 4.

Now, we need to draw the minimal dfa such that no. of 0's is divisible by 4 and no. of 1's is odd.

Now if you try to draw for k, then you will have k state in the first row.

To match odd no. of 1's you will have k state in the second row.

Total no. of states is 2k.

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
Bikram asked Aug 12, 2017
463 views
Consider the following transition table of DFA where $q3$ is the final state:$\begin{array}{|c|c|c|} \hline {} & x & y \\ \hline \rightarrow q0 & q1 & q0 \\ \hline q1 & q...
1 votes
1 votes
1 answer
2
Bikram asked Aug 12, 2017
577 views
Consider the following input sequence $010101\dots$ ($01$ repeated one or more times).The minimum number of states required in a DFA to accept the strings following the a...
1 votes
1 votes
1 answer
4
Bikram asked Aug 12, 2017
259 views
How many states does the Minimal Finite Automata that accepts all strings of $x$'s and $z$'s (where the number of $x$'s is at least $L$) contain?$L$ states$(L+1)$ states$...