I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive be considered part of a regular set? Lets say I have that same set, but instead of being even, they are divisible by some number (how about 3), would it still be a regular set?
I've been looking at this helpful guide I found online, but I'm still confused about what can be defined as a regular set: link below
$\endgroup$2 Answers
$\begingroup$Corrected.
A binary string $b_n\ldots b_0$ is the binary representation of a positive even integer if and only if $b_0=0$ and $n\ge 1$. The regular expression $(0+1)(0+1)^*0$ generates precisely this set of strings, since $(0+1)(0+1)^*$ generates the set of all non-empty binary strings. Thus, the set of bit strings that represent positive even integers when interpreted as binary numbers is a regular set.
More generally, if $n$ is any positive integer, the set of binary representations of the multiples of $n$ is a regular set. This is probably easiest to see by showing how to construct a DFA $M$ that recognizes this set of bit strings. It will have states $q_k$ for $k=0,\ldots,n-1$, $q_0$ being the initial state and the only acceptor state. The idea is that $M$ is in state $q_k$ when the number corresponding to the bits read up to that point is congruent to $k$ mod $n$. The $0$-transition out of $q_k$ goes to $q_{2k\bmod n}$, and the $1$-transition out of $q_k$ goes to $q_{(2k+1)\bmod n}$.
By changing the set of acceptor states we can modify $M$ to accept the binary representations of any congruence class mod $n$, or indeed of any union of those classes.
$\endgroup$ 2 $\begingroup$Whether a set is a "regular set" is only really defined if the set is a set of strings. For sets of integers, I suppose you could say that a set of integers is regular if and only if the set of the strings you get when you write the integers in some base $b$ is regular, but then your definition depends on the base you use!
(E.g., there are infinite sets of integers that form regular sets when written out in base $2$ that do not form regular sets when written out in base $3$ and vice versa)
Ultimately, what can be a regular set boils down to the definitions of regularity (DFAs and regular expressions) and the theorems that are used to prove/disprove regularity.
$\endgroup$
