Bruce force stategy on finite state diagrammachine 01 Soluti

Bruce force stategy on finite state diagram/machine?

Solution

In general the machine will accept all sequences that can be described by the computational grammar

The only new features are the use of <null> to specify the starting state and the use of # to specify the final state. You can have many hours of happy fun trying to prove that this grammar parses the same sequences as the finite state machine accepts.

To see that it is it does just try generating a sequence:

You can carry on using rule 2 and 3 alternately until you get bored and decide to use the A# alternative of rule 3 giving something like BABABABAA#.

can represent a finite state machine in a form that makes it easier to understand and think about.

All you have to do is draw a circle for every state and arrows that show which state follows for each input symbol.

For example, the finite state machine in the diagram below has three states. If the machine is in state 1 then an A moves it to state 2 and a B moves it to state 3.

This really does make the finite state machine look very simple and you can imagine how as symbols are applied to it how it jumps around between states.