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 ![Rendered by QuickLaTeX.com 0](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-3faf070225faa3d2f8e5592870e1a387_l3.png)
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
.
Old Ternary | Old Decimal | ![]() | Symbol | New Ternary | New Decimal | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Symbol ![Rendered by QuickLaTeX.com 1](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-2c261c8cfdeddc42ac719c047507d0b8_l3.png)
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
.
Old Ternary | Old Decimal | ![]() | Symbol | New Ternary | New Decimal | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Symbol ![Rendered by QuickLaTeX.com 2](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-65a43007889ad455af38aa6bc8bbef25_l3.png)
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
.
Old Ternary | Old Decimal | ![]() | Symbol | New Ternary | New Decimal | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
General Formula
Consider any ternary string , that leaves remainder
when divided by
. Upon seeing a new symbol after
, the remainder changes as follows
Ternary String | Remainder | New Symbol | New Remainder |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
can take values from
to
. Substituting these values in the above table, generates the following
Remainder | New Symbol | New Remainder |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
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
From State | Symbol | To State |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
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