3 ms·
An important example from CS would be the semigroup action on the set of states of a deterministic finite automaton. The action takes a state from Q, and a sym
by chobytes 6y ago
An important example from CS would be the semigroup action on the set of states of a deterministic finite automaton.
The action takes a state from Q, and a symbol from E, and returns a new state. ie f:QxE->Q.
In the case when you have some "no op" action the semigroup action is actually a monoid action.
This all corresponds to the DFA moving through states as it "eats" the string.
- raphlinus 6y agoYupyup. For those of us who don't just automatically know what a semigroup action is, Dan Piponi's blog on using monoids to do incremental regular expression matching is probably a good read: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html http://blog.sigfpe.com/2009/01/fast-incremental-regular-expr...