Consider the problem of building a Nondeterministic Finite Automaton (NFA) over to accept ternary numbers that are a multiple of but not a multiple of . Here are the first ternary numbers.

Ternary	Decimal
	0
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	17
	18

Multiples of 3

From the above table, the ternary numbers that are a multiple of always end with a . Notice that, is indeed a multiple of .

Multiples of 9

From the above table, the ternary numbers that are a multiple of always end with a . Notice that, is indeed a multiple of .

Multiples of 3 but not a Multiple of 9

Extrapolating from the previous two observations, the ternary numbers that are a multiple of but not a multiple of are numbers that end with a single . Thus, the last two digits can be either or . The digits before these two digits do not matter.

Regex

A regular expression to express this would be

NFA

The above regular expression can expressed as the following NFA