A NFA accepting ;anguages whose final digit didn't appear before

Question

Give a non-deterministic finite automata(NFA) which accepts the following language: The set of strings over the alphabet {0,1,...,9} such that the final digit has not appeared before. I have encountered this problem on introduction to automata theory languages and computation page 67 Exercise 2.3.4

Answer 1

When the alphabet is {0,1}, which is the simplest non-trivial situation, we can get a simplest NFA like this: The simplest non-trivial situation So further you can get an NFA like this: enter image description here

Answer 2

An easy way to get an NFA for this is to consider each of the 10 cases separately. Consider the case of all strings in the language whose last digit is 0. Such strings contain no other 0s; a regular expression for them is (1+2+3+4+5+6+7+8+9)*0. An NFA for them looks sort of like

  1,2,3,4,5,6,8,9
       /--\
       |  /
       V /
o----->A0--0-->[B0]

We can imagine 9 others with states Ax, Bx, where Bx is accepting for each x, and Ax loops to itself on every symbol besides x, and to Bx on symbol x.

We can then glue all of these together by introducing a new initial state S which has an empty/lambda transition to the Ax states. The final NFA would have:

• one initial state S
• empty/lambda/epsilon transitions from S to states A0, A1, A2, A3, A4, A5, A6, A7, A8 and A9
• transitions from A0 to B0 on 0, A1 to B1 on 1, A2 to B2 on 2, and so on
• all missing transitions from states A0, A1, A2, and so on, back to those same states

In fact, why not copy/paste the above and just write the whole thing down?

       1,2,3,4,5,6,7,8,9
            /--\
            |  /
            V /
     /----->A0--0-->[B0]
    /
   |   0,2,3,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A1--1-->[B1]
   |/
   |   0,1,3,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A2--2-->[B2]
   |/
   |   0,1,2,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A3--3-->[B3]
   |/
   |   0,1,2,3,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A4--4-->[B4]
   |/
   /   0,1,2,3,4,6,7,8,9
S-<         /--\
   \        |  /
   |\       V /
   | \----->A5--5-->[B5]
   |
   |   0,1,2,3,4,5,7,8,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A6--6-->[B6]
   |
   |   0,1,2,3,4,5,6,8,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A7--7-->[B7]
   |
   |   0,1,2,3,4,5,6,7,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A8--8-->[B8]
   |
   |   0,1,2,3,4,5,6,7,8
   |        /--\
   |        |  /
    \       V /
     \----->A9--9-->[B9]

Is this the simplest NFA or DFA for this language? Almost surely not. But it should work.