Language recognized by Finite automata?

602 Views Asked by At

I'm trying to figure out what language does this finite automata accept.

The machine accepts: 1, 1010, 00, 01010 .... etc

The machine rejects: 0, 010, 10, 11 .... etc

So my guess is L(M) accepts the regular expression 1+(01)+00

What do you think? Can you help with a regular expression or any description of what could this machine take please?

enter image description here

1

There are 1 best solutions below

0
On

You can use vertex removal.

For example, $D$ can only be entered from $C$, so we can remove it. This means we must merge some transition edges. The ways we pass through $D$ is $C\to D\to B$ or $C\to D\to C$

So in place of the ingoing/outgoing edges at $D$, we will not have a loop edge labeled $00$ at $C$ and an edge labeled $01$ going from $C$ to $B$.

When labeling edges, remember to label them with regular expressions that result from merging appropriate edges.

Of course, be aware that one state is the start state, in this case it is $A$. Don't remove it.