Further Study of Finite State Machines

Finite State Machines in Parallel

Two finite state machines can be run in parallel . The same input is fed to both machines, and the input is not considered accepted unless the input produces the accept state in both machines. Try running these two machines in parallel:

and

Figuring out what will be accepted by two machines is a complicated process, and it is certainly more difficult than figuring out what is accepted by a single machine. Begin by listing the inputs that are accepted by both machines. Look for patterns and make other observations as you experiment with various inputs. What are some of the strategies that you end up using to figure it out? Can you draw a single finite state machine that does the same thing as these two finite state machines running in parallel?

Experiment with other finite state machines running in parallel, and note your observations. Do you think that it is possible to set up two finite state machines running in parallel and have it turn out that they don't accept any inputs.

Same or Different Machine?

It is not unusual to be able to draw two different finite state machines that both accept and reject the same input words. Here are two examples:

What is it about these two finite state machines that makes them behave the same even though they look different?

Can you draw other finite state machines that behave the same but look different?