0
$\begingroup$

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$}.
(Please suggest answers; not hints.)

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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\}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Say, how can I write this as an NFA if I wanted? @Nathaniel? $\endgroup$
    – NiStack
    Commented Apr 6, 2023 at 20:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – Nathaniel
    Commented Apr 6, 2023 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.