Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$

It is needed to give a general method to construct an automaton which accepts this language. I'm trutly lost about the procedure in this. Any hint would be helpful.

Some observations about this: The automaton is not specified (i.e. could be NFA or DFA) and the numbers are static.


Your automaton will have $k$ states, one for each possible value of $m$, i.e., one for each of the congruence $(\text{mod } k)$ classes. Exactly one of these states will be marked as the final state, because that will be the one that accepts ocurrences of $\alpha$ that are compatible with $x ( \text{mod } k) =m$.

The transition function will connect states representing congruence classes for $m=a$ and $m=b$ by an arrow labeled with a symbol denoting $c$, if and only if $(a.p +c)\text{ mod } k = b$.

The initial state will be the one corresponding to $m = 0$, assuming leading zeros are allowed.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.