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

209 Views Asked by At

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?

enter image description here

EDIT

enter image description here

1

There are 1 best solutions below

8
On BEST ANSWER

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.