Explore BrainMass

Strings recognized by deterministic finite-state automaton

Determine whether each of these strings is recognized by the given deterministic finite-state automaton (which is displayed in an attached .doc file):

(a) 010
(b) 1101
(c) 1111110
(d) 010101010


Solution Preview

The set of states recognized by the finite-state automaton are those that reach one of the "final" states.

The final states are those which are designated in the diagram by a pair of concentric circles (namely, s_0 and s_3).

Thus we consider what happens when each of the given strings is input to the automaton.

Regardless of the input, the automaton starts in state s_0, and it reads the bits in the input string from left to right.


(a) 010

Step 1: The machine reads a 0 (the 0 on the left), and remains in state s_0 (see the "loop" in the diagram).

Step 2: The machine reads a 1, then goes from state s_0 to state s_1 (see the arrow with the "1", directed from state s_0 to state s_1).

Step 3: The machine reads a 0, then goes back to s_0 (see the arrow with the "0", directed from state s_1 to state s_0).

Since all the bits of the input string have been read, the machine ends up in state s_0, which is a final state, so the machine does recognize the ...

Solution Summary

For each string, every step which is executed by the automaton (when that string is input to it) is analyzed in detail.
The results of that analysis are used to determine which of the strings are recognized by the automaton.