patternMinor
Language of the values of an affine function
Viewed 0 times
thefunctionlanguagevaluesaffine
Problem
Write $\bar n$ for the decimal expansion of $n$ (with no leading
$$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$$
Is $M$ regular? context-free?
(Contrast with Language of the graph of an affine function)
I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.
0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions of the multiples of $a$ plus a constant:$$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$$
Is $M$ regular? context-free?
(Contrast with Language of the graph of an affine function)
I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.
Solution
Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with $a$ states 0, 1, ..., $a - 1$. Start state is 0, and from state $q$ on input the digit $d$ go to state $(10 q + d) \bmod a$. Accepting state is $b \bmod a$ (might need a tweak if $b > a$).
Context
StackExchange Computer Science Q#640, answer score: 9
Revisions (0)
No revisions yet.