You can describe an FSM with a diagram, or you can just keep track of the transitions. For this FSM you would need 6 people, one for each state. Tape the name of their state to their shirt, or use some other method to label the states. You could even rename the states so the name of each state is the name of the person representing it. The activity is run just as before.
People enter the machine at the start state with their word.
Then that person would go to wherever the person lablelled B is, and repeat the process with the next letter. Have everyone try to invent words that will be accepted by this machine. You might suggest that people try to make diagrams of the machine as they work. As easy way to make this activity more difficult is to let the 'states' wander around, so that people working the machine can't identify the different states with physical locations. If you like role-playing in your activity, note that the states can be like states of minds, or moods.