DFA creation and minimization

Task: Draw an DFA that accepts words from the alphabet {0,1} where the last character is not repeated anywhere else in the word. (example: words 0, 1, 00001, 111110, ε are in the language of this NFA, while words 010, 111, 0010, 101 are not).

I think I got the DFA right but I can't minimize it because I have a trap state which I can't get rid of whatever I do. Any advices or tips?

Your DFA is correct (except the initial state q0 should be accepting since the empty string is in the language). It is also minimal; we can show that the sets of strings that lead to each state are all distinguishable w.r.t. the language according to the Myhill-Nerode indistinguishability relation.

• q0: any string in L can be appended to the strings that lead here (the empty string) to get another string in L

• q1: appending the string 0 in L to 0 gives 00 not in L, so q1 is distinct from q0.

• q2: appending the string 1 in L to 1 gives 11 not in L, so q2 is distinct from q0 and from q1 (since appending 1 to 0 gives 01 which is in L also)

• strings that lead to q3 are distinct from q1 in that you cannot append the empty string (i.e., q1 is accepting and q3 isn't), but otherwise identical, and therefore q3 is also distinct from q0-q2

• strings that lead to q4 are distinct from q2 in that you cannot append the empty string (i.e., q2 is accepting and q4 isn't), but otherwise identical, and therefore q4 is also distinct from q0-q2

• appending anything but the empty string to strings that lead to q5 leads to a string not in the language, so it is distinct from q0-q4

• appending anything to a strings that lead to q6 leads to a string not in the language, so it is distinct from q0-q5 (these strings differ from strings that lead to q5 only in that you cannot even append the empty string to them to get a string in L, i.e., q6 is not accepting and q5 is).

Therefore, your DFA is minimal. You can show this by attempting to run a minimization algorithm and noting that no states get removed.

Note: it depends on your definitions but it is a normal (and I would say preferred) definition of DFAs that they define all transitions, which means that dead (or as you call them, trap) states are required to be shown. Minimization algorithms probably don't remove them, but you can remove them if you like (though I'd call the resulting automaton nondeterministic since deterministic behavior is not specified for some transitions).