# Designing a DFA with nth character condition for any integer n

Let n be an integer. How can I write finite automata for the language L?
L = {W∈{$$0,1,2$$}*| The $$n_{th}$$ from last letter in w is $$0$$}.

Attempt
Using Regex, I could write it as $$[012]*0[012](n - 1)$$ - replacing n - 1 with the actual integer value. But I'm not sure of a good program to diagram it with.

It is possible to prove that such a DFA would always have at least $$2^n$$ states (the idea of the proof is given here, but for a two-letters alphabet).

This bound can be reached: consider $$A = (Q, \delta, q_0, F)$$ where:

• $$Q = \{0,1\}^n$$: to each state corresponds a word of length $$n$$ over the alphabet $$\{0,1\}$$;
• $$q_0 = 1^n$$;
• $$F = \{0u\mid u\in \{0,1\}^{n-1}\}$$: states that begin with $$0$$;
• for $$u\in \{0,1\}^n$$, $$u = u_1…u_n$$, $$\delta(u, 0) = u_2…u_n0$$ and $$\delta(u,1) = \delta(u, 2) = u_2…u_n1$$.

The idea is that each state tells you what are the last $$n$$ letters you read (at least for words of length $$\geqslant n$$), with $$2$$'s being associated with $$1$$'s (we just need to know the positions of $$0$$'s).

Proof left to you that $$L(A) = \{w\in\{0,1,2\}^*\mid w = u0v, \text{ with }|v| = n-1\}$$.

• Say, how can I write this as an NFA if I wanted? @Nathaniel? Apr 6, 2023 at 20:01
• @NitayStack Add a cycling transition with any letter on the initial state, then a transition labeled with $0$ to the second state, then a line of $n-1$ states, each one with a transition to the following, labeled with any letter, the last one being the only ending state. Apr 6, 2023 at 20:36