A state machine is not associated with execution semantics between states. All a state machine does is presenting transitions between states and the logic occurring validating and running during transitions.
The logic running during a transition itself can be run in parallel, by spawning new threads for example. The threads can run asynchronously to the execution or they can be spawned, then joined back to the main thread as part of the main thread.