"We define a two-step learner for RFSAs based on an observation table by using an algorithm for minimal DFAs to build a table for the reversal of the language in question and showing that we can derive the minimal RFSA from it after some simple modifications. We compare the algorithm to two other table-based ones of which one (by Bollig et al. 2009) infers a RFSA directly, and the other is another two-step learner proposed by the author. We focus on the criterion of query complexity."

"We study several problems related to finding reset words in deterministic finite automata. In particular, we establish that the problem of deciding whether a shortest reset word has length k is complete for the complexity class DP. This result answers a question posed by Volkov. For the search problems of finding a shortest reset word and the length of a shortest reset word, we establish membership in the complexity classes FP^NP and FP^NP[log], respectively. Moreover, we show that both these problems are hard for FP^NP[log]. Finally, we observe that computing a reset word of a given length is FNP-complete."

"Ragel compiles executable finite state machines from regular languages. Ragel targets C, C++, Objective-C, D, Java and Ruby. Ragel state machines can not only recognize byte sequences as regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language. Code embedding is done using inline operators that do not disrupt the regular language syntax."

"But enough of irony. Is this useful? I think it may be. You see, one of the great benefits of describing a problem as a Finite State Machine (FSM) is that you can complete the logic of the problem. That is, if you can enumerate the states and the events, then you know that the number of paths through the system is no larger than S * E. Or, rather, there are no more than S*E transitions from one state to another. More importantly, enumerating them is simply a matter of creating a transition for every combination of state and event.

One of the more persistent problems in BDD (and TDD for that matter) is knowing when you are done. That is, how do you know that you have written enough scenarios (tests). Perhaps there is some condition that you have forgotten to explore, some pathway through the system that you have not described."

Rails plugin to add FSM functionality to models