MHB What Automata Accepts Binary Numbers Divisible by $2 ^ k$?

[mathmari]

Hey!

"Give the definition of a FA (without a graphical representation), which accepts binary numbers $n$ which are without remainder divisible by $2 ^ k$ for all $k \in \mathbb{N} \setminus \{0\}$."

Could you help me understanding which automata is meant?

 

[I like Serena]

Hey!

"Give the definition of a FA (without a graphical representation), which accepts binary numbers $n$ which are without remainder divisible by $2 ^ k$ for all $k \in \mathbb{N} \setminus \{0\}$."

Could you help me understanding which automata is meant?

Hi! :)

That looks a bit like a trick question, or else it is worded badly.
Is that the literal problem statement?

Whichever number $n \ne 0$ you pick, there will always be a $k$ such that $2^k > n$.
If we divide that $n$ by $2^k$ the remainder is $n$, so $n$ does not qualify.

Taken literally, only numbers of the form $0+$ qualify.

 

[mathmari]

I looked again the exercise and thought the following:

$\begin{matrix}
Dual & Binary \\
0 & 000000 \\
1 & 000001 \\
2 & 000010 \\
3 & 000011 \\
4 & 000100 \\
5 & 000101 \\
6 & 000110 \\
7 & 000111 \\
8 & 001000 \\
9 & 001001 \\
10 & 001010 \\
... & ...
\end{matrix}$

Each number is divible by $2$ if the remainder of the division by $2$ is $0$.
The possible remainders of the division by $2$ are: $0,1$.

$\begin{matrix}
0 \overset{0}{\rightarrow}00( \text{ The rest is 0})\\
0 \overset{1}{\rightarrow}01( \text{ The rest is 1})\\
\\
01 \overset{0}{\rightarrow}010( \text{ The rest is 0})\\
01 \overset{1}{\rightarrow}011( \text{ The rest is 1})\\
\\
011 \overset{0}{\rightarrow}0110( \text{ The rest is 0})\\
011 \overset{1}{\rightarrow}0111( \text{ The rest is 1})\\
\\

\end{matrix}$

So the DFA is the following:
View attachment 2250

Is this correct?

 

[I like Serena]

I looked again the exercise and thought the following:

$\begin{matrix}
Dual & Binary \\
0 & 000000 \\
1 & 000001 \\
2 & 000010 \\
3 & 000011 \\
4 & 000100 \\
5 & 000101 \\
6 & 000110 \\
7 & 000111 \\
8 & 001000 \\
9 & 001001 \\
10 & 001010 \\
... & ...
\end{matrix}$

Each number is divible by $2$ if the remainder of the division by $2$ is $0$.
The possible remainders of the division by $2$ are: $0,1$.

$\begin{matrix}
0 \overset{0}{\rightarrow}00( \text{ The rest is 0})\\
0 \overset{1}{\rightarrow}01( \text{ The rest is 1})\\
\\
01 \overset{0}{\rightarrow}010( \text{ The rest is 0})\\
01 \overset{1}{\rightarrow}011( \text{ The rest is 1})\\
\\
011 \overset{0}{\rightarrow}0110( \text{ The rest is 0})\\
011 \overset{1}{\rightarrow}0111( \text{ The rest is 1})\\
\\

\end{matrix}$

So the DFA is the following:
https://www.physicsforums.com/attachments/2250

Is this correct?

Your DFA would properly accept a binary number that has no remainder when divided by 2. (Emo)

However, the problem statement requires that the binary number should also have no remainder when divided by 4.
Nor when divided by 8, 16, 32, ... ad infinitum.
I do see that your DFA could be modified to allow for that.
Effectively it would only accept a string of 1 or more zeroes.

Btw, the problem statement asks for an FA without graphical presentation. So it should be in the form of a set of rules together with their context.

 

[DavidCampen]

Terminology change?

I am familiar with the term Finite State Machine, it seems that FA (Finite Automaton) means the same thing. I had not heard the term Finite Automaton before. Has the terminology changed, is the term FA now preferred over the term FSM; if so, what is a Turing Machine now called?

 

[Evgeny.Makarov]

The books "Elements of the Theory of Computation" by Lewis and Papadimitriou and "Introduction to the Theory of Computation" by Sipser use the term "finite automaton", though they say that "finite state machine" is a synonym. The Wikipedia page is called "Finite-state machine", but it also mentions automata. I don't think either term is a new trend. Turing machines are still Turing machines.

 

[DavidCampen]

Well, I guess that "new" is relative. My knowledge is 30 years old. At least they haven't started calling a "Turing Machine" a "Turing Automaton"; next we would have to change "Association for Computing Machinery" to "Association for Computing Automatons".