0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Can you give me a word which is wrong with my automata? $\endgroup$
    – John
    Feb 15, 2021 at 20:12
  • $\begingroup$ @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. $\endgroup$ Feb 15, 2021 at 20:14
  • $\begingroup$ Can you show an example of a diagram which will work? $\endgroup$
    – John
    Feb 15, 2021 at 20:16
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 15, 2021 at 20:26
  • 1
    $\begingroup$ @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 $\endgroup$
    – hgmath
    Feb 15, 2021 at 21:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .