We are constructing a deterministic finite automaton (DFA) that judges whether the sum of two binary integers is a multiple of three or not.
(1) A DFA is represented by a directed graph called a state diagram. Figure 1 is an example of a state diagram. The states of a DFA are represented by the nodes of the graph. When a DFA in state reads a symbol , it changes its state according to the outgoing edge labeled of the node corresponding to . The set of allowed input symbols is a finite set, which is called its input alphabet. In the state graph of a DFA, each node has exactly one outgoing edge for each symbol in its input alphabet.
One of the states is the start state, which is indicated by the arrow labeled start. Some states are designated as final states, which are indicated by double circles. When a DFA in its start state will be in one of the final states after reading all symbols of a symbol string one-by-one from left to right, we say accepts .
(1-1) Let be the DFA represented by Figure 1. The input alphabet of is .
Answer the state that will be in after reading the symbol string 0101110 starting in the start state.
(1-2) Answer the shortest symbol string starting with 0101110 that the DFA accepts.
(1-3) Construct a DFA that accepts a symbol string if and only if the length of is an even number, and draw its state diagram. must satisfy the following conditions.
(Condition 1) The number of states of is two.
(Condition 2) The input alphabet of is .
(2) Consider a string of symbols in to be a binary number. Let denote the -digit binary number whose -th digit from the least significant digit is . Let denote its value. When the string starts with a sequence of 0s, let denote the value of the string without the sequence of 0s. The string whose length is zero is called an empty string, denoted by . Let . For example, is 46 in decimal.
For every binary number with an even number of digits , show
Here, "" denotes the remainders of and are the same when they are divided by three. In what follows, we will omit " " and simply denote "."
(3) Consider , a string of symbols in , to be a binary number . Construct a DFA that accepts , the string in reverse order, if and only if its length is an even number and
holds, and draw its state diagram. must satisfy the following conditions.
(Condition 1) The number of states of is six.
(Condition 2) The input alphabet of is .
(4) Consider , a string of symbols in , to be a binary number . Construct a DFA that accepts if and only if
holds regardless of the length of , and draw its state diagram. must satisfy the following conditions.
(Condition 1) The number of states of is three.
(Condition 2) The input alphabet of is .
(5) Let
For , a string of symbols in with length , construct a DFA that accepts if and only if
holds, and draw its state diagram. must satisfy the following conditions.
(Condition 1) The number of states of is three.
(Condition 2) The input alphabet of is .
