# Is it possible to shorten this Finite Automata Transition Graph?

I designed this transition graph, seen below. The alphabet contains {a, b, c}, and the goal of this machine is to accept any strings (no limitations on length of string) that ends with a letter that is already in that string.

Example: abba, aaa, bb, ababababacc, cabc are accepted. Example: abc, bccba, a, b, c, cccab, are a rejected.

Is there a shorter/simpler way to design this finite automata than this transition graph?

• What have you tried? Any decent textbook should tellyou how to minimize a DFA. Have you tried that? – D.W. Sep 26 '15 at 5:14
• While this is an NFA, where minimization is harder, you can still identify and merge states which are bisimilar. In particular, your states $q10,\dots,q15$ are all essentially equivalent; after merging these, you can do the same to the pairs $(q4,q6),(q5,q8)$ and $(q7,q9)$. – Klaus Draeger Sep 26 '15 at 9:57

Each string that is input to an automaton takes you to some state. So you can see each state an encoding some kind of information about the inputs the machine has seen if it's in that state. For example, an automaton might have a state that corresponds to "all words with an even number of $b$s."
For your task, think about a regular expression $(a+b)^*c(a+b+c)^*c$ as corresponding to only one of the possible cases, viz. the case which only finds the words having $c$ repeated at least twice. You may use the same idea to construct automata for $a$ and $b$, and then take the union of the three. The resulting graph will be roughly the half of what you have now.
• That regular expression isn't any of the cases. It matches $cca$, which isn't in the language. – David Richerby Sep 26 '15 at 11:14