Learning finite state models of observable nondeterministic systems in a testing context

Learning models from test observations can be adapted to the case when the system provides nondeterministic answers. In this paper we propose an algorithm for inferring observable nondeterministic finite state machines (ONFSMs). The algorithm is based on Angluin L* algorithm for learning DFAs. We define rules for constructing and updating learning queries taking into account the properties of ONFSMs. Application examples, complexity analysis and an experimental evaluation of the proposed algorithm are provided.