# Ternary representation of an integer that is a multiple of 5

Consider the problem of building a Deterministic Finite Automaton (DFA) over to accept ternary numbers that are multiples of 5. For the sake of simplicity, assume that the empty string, , should be accepted.

## States

The resulting DFA will have states. Each state will keep track of one of five possible remainders – .

For example, the state , keeps track of the information that the ternary string read upto this point, when divided by , leaves remainder .

## Tracking remainder

Consider the ternary string . The decimal equivalent of this ternary number is . when divided by , leaves remainder . Thus, if the above DFA already read the input , it will currently be in state .

## Symbol

If the string is followed by a , the ternary number is equivalent to in decimal. In effect, seeing a single at the end of a ternary string, multiplies the integer equivalent by . The same logic applies to the remainder. when divided by , leaves remainder , which is the same as .

## Symbol

If the string is followed by a , the ternary number is equivalent to in decimal. In effect, seeing a single at the end of a ternary string, multiplies the integer equivalent by and then adds a . The same logic applies to the remainder. when divided by , leaves remainder , which is the same as .

## Symbol

If the string is followed by a , the ternary number is equivalent to in decimal. In effect, seeing a single at the end of a ternary string, multiplies the integer equivalent by and then adds a . The same logic applies to the remainder. when divided by , leaves remainder , which is the same as .

## General Formula

Consider any ternary string , that leaves remainder when divided by . Upon seeing a new symbol after , the remainder changes as follows

can take values from to . Substituting these values in the above table, generates the following

## Transitions

In the above table, the first column maps to one of the states of the DFA. The second column, maps to a transition symbol. The third column maps to the state the transition points to. Converting the table to states and transitions results in

Since, the DFA has to accept strings that are multiples of , the state will be the only final state.

## DFA

Combining the states and the transition table, the resulting DFA is shown below