4
$\begingroup$

What does happen if two events simultaneously occur at a particular state of a finite state automaton (FSA)?

For example, assume that an FSA's event table at its state $s$ is as follows:

$\delta(s,e_1)=s_1$ and $\delta(s,e_2)=s_2$. What will be the system's next state if both $e_1$ and $e_2$ occur exactly at the same time?

$\endgroup$
4
$\begingroup$

Finite-state automata take a sequence of events as input. There is a single event in the input sequence at any given position. What if there are two different values at position 3 in the sequence $ababcaccab$? There aren't, that's just how the mathematical object is constructed.

The input to a FSA is not necessarily a sequence of events that happen one after the other. For example, when an FSA is used for string parsing, there's no concept of time. But let's assume that you're using an FSA as part of a model of something that reacts to events over time. Note that this is no longer just about automata theory, but also about what you're modeling. What if you want to express that two events are simultaneous? Then you'll need to use a more sophisticated mathematical tool.

The core of the mathematical tool can still be a finite state automata, but instead of taking a sequence of events as input, you'd take a sequence of sets of events. The thing is, in practice, this is rarely useful, because in practice, things do not happen simultaneously. At most, they happen simultaneously up to measurement error. Given that measurement error is, by definition, variable, the same physical process may or may not be observed as simultaneous if you try it again several times. Therefore it is not useful to consider simultaneity in the model: it brings extra complexity to the math without providing any extra insights regarding the physical process.

Simultaneity is a useful concept regarding events that have a duration: event A may end after event B starts, in which case events A and B overlap. But if you're interested in that, then you can't model A and B as single events, you need to distinguish separate events “A starts, B starts, A ends, B ends”. These start/end events happen sequentially.

There is one world where things do happen sequentially, which is the world of discrete time. Discrete time is used to model digital circuits (because it corresponds to how they work). Two events may happen during the same clock cycle; that's the definition of simultaneous here. A digital circuit is modeled as a finite state automaton in a straightforward way, but then each element in the input sequence is not an individual event such as “input 42 switches from 0 to 1”, but a collective event made of the state of all the states of all the inputs.

$\endgroup$
3
$\begingroup$

As far as I know a finite automaton (FA) may read only one input at a time, either $e_1$ or $e_2$ and hence the FA is in either $s_1$ or $s_2$.

$\endgroup$
2
$\begingroup$

Concurrency is not part of the finite automaton model (just check the definition), nor in any finite-state system I'm aware of. When implementing one, you would serialize incoming events.

You could define a new model that, in each state, accepts a set of input symbols/events. What happens is up to you, or part of the transition function. You'll see that your model does not become any more powerful (it's just a larger alphabet) so the theory behind this is probably not very interesting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.