1
$\begingroup$

This is the automaton I want to find the regular expression for:
an automaton with 5 states

As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 consecutive zeros.
Can anybody help finding a regular expression for this?

Note : What I tried ...
I defined A:=(0+00+000)
So the automata accepts the strings which contain no consecutive A's. But I don't know how to find that kind of regular expression.

| cite | improve this question | |
$\endgroup$
0
$\begingroup$

Hint: A string with no more than 3 consecutive zeroes has the general form $$0^{p_1} 1 0^{p_2} 1 0^{p_3} 1 \ldots,$$ where $p_i \leq 3$. Try expressing that structure as a regular expression.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.