0

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

John
  • 21

1 Answers1

1

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.

Brian M. Scott
  • 616,228
  • Can you give me a word which is wrong with my automata? – John Feb 15 '21 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. – Brian M. Scott Feb 15 '21 at 20:14
  • Can you show an example of a diagram which will work? – John Feb 15 '21 at 20:16
  • @Ulice: At the moment I don’t have the software to produce a diagram; that’s why I explained in detail how the automaton should work when the first input is $0$. You should be able quite easily to translate that verbal description into a diagram and to design and draw the other branch of the automaton (for an initial input of $1$). – Brian M. Scott Feb 15 '21 at 20:23
  • I have modified my question. I think the second diagram should work. Is it optimal? It is not deterministic, but the question doesn't it anw. – John Feb 15 '21 at 20:25
  • 1
    @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. – Brian M. Scott Feb 15 '21 at 20:26
  • 1
    @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 – hgmath Feb 15 '21 at 21:44
  • @hgmath: Ah, of course; thanks! (You can see how little time I spent thinking about it!) – Brian M. Scott Feb 15 '21 at 21:46