alphabet $\{0, 1\}$, the set of non-empty words whose first letter occurs at least two other times

Build finite automata that accept the language: the alphabet $$\{0, 1\}$$, the set of non-empty words whose first letter occurs at least two other times. Automata can be non-deterministic if that makes it easier for you. However, you cannot use transitions labeled with a regular expression or the empty word $$\epsilon$$.

I made this finite automata, but it seems to be wrong. Can you tell me what would be a good automata for this exercise?

EDIT

It is indeed wrong: it accepts every non-empty word over the alphabet $$\{0,1\}$$. It’s actually just as easy to make the automaton deterministic. (By the way, automata is plural: the singular is automaton.) Like your attempt, it will have two independent tracks, one for a first letter $$0$$ and one for a first letter $$1$$.

The $$0$$ track will have states $$q_1,q_2$$, and $$q_3$$. Starting at $$q_0$$ there should be a $$0$$ transition to $$q_1$$ to start the track. A $$1$$ input at $$q_1$$ should just loop at $$q_1$$, and the $$0$$ transition should go to $$q_2$$. (Note that the subscript shows how many zeroes the automaton has read so far.) A $$1$$ input at $$q_2$$ should simply loop at $$q_2$$, and the $$0$$ transition should go to $$q_3$$, which should be an acceptor state. Both possible inputs should simply loop at $$q_3$$.

The $$1$$ track is very similar.

• Can you give me a word which is wrong with my automata?
– John
Feb 15, 2021 at 20:12
• @Ulice: It accepts $0$. It accepts $01111$. As I said, it accepts every non-empty word, not just the ones that have at least $3$ instances of the first letter. Feb 15, 2021 at 20:14
• Can you show an example of a diagram which will work?
– John
Feb 15, 2021 at 20:16
• @Ulice: Yes, that’s exactly the automaton that I had in mind. I suspect that it is optimal among DFAs, though I’ve not actually tried to prove this. Feb 15, 2021 at 20:26
• @BrianM.Scott the states q3 and q6 can of course be merged... but after doing this the DFA will indeed be minimal because then all the states would be distinguishable Feb 15, 2021 at 21:44