Create NFA where the second symbol of the string is the same with the last symbol

Question

I have tried:

Let $L= \{a,b,c,d, \dots, z\}$. Create NFA where the second symbol of the string is the same with the last symbol.

How do I solve this? Should I do repeatedly until $z$?

Answer 1

My solution might not be the smallest automaton, but it works. We will introduce states named: $0, 1, A_1 ... Z_1, A_2 ... Z_2, A_3 ... Z_3$. $0$ is the start state. $A_1 ... Z_1$ and $A_2 ... Z_2$ are accepting. The intuition is this:
$\bullet$ $0$ means we read no characters.
$\bullet$ 1 means we read only one character.
$\bullet$ $A_1 ... Z_1$ means the word we read is only two characters long which means it surely must satisfy the condition.
$\bullet$ $A_2 ... Z_2$ means the word is longer than two characters, but satisfies the condition.
$\bullet$ $A_3 ... Z_3$ means the word is longer than two characters and doesn't satisfy the condition.
The letter in state name $A_1/A_2/A_3$ indicates the 2nd character of the word.
Now the transitions are as follows:
$\bullet$ From $0$ you go to $1$ on any input.
$\bullet$ From $1$ on $a/b/.../z$ you go to $A_1/B_1/.../Z_1$.
$\bullet$ From $A_1$ on $a$ you go to $A_2$, on any other input you go to $A_3$ (the same for other characters).
$\bullet$ From $A_2$ on input $a$ you go do $A_2$, on any other input you go to $A_3$ (the same for other characters).
$\bullet$ From $A_3$ on input $a$ you go to $A_2$, on any other input you go to $A_3$ (the same goes for other characters).
Why does dhis work?
For simplicity let's assume we just focus on the 2nd letter being $a$. The first character is of no interest. Then we read the character $a$ and our condition is satisfied, since we have a word $?a$. Now if we read another $a's$, then our word surely ends on the same character as the 2nd one. If we read anything else, then the condition is not satisfied, and only reading an $a$ again, can make the word end in the same character as the 2nd one.