patternMinor
Finite state automaton's reaction to simultaneous events
Viewed 0 times
finiteeventssimultaneousstateautomatonreaction
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#83942, answer score: 3
Revisions (0)
No revisions yet.