  Non-deterministic Finite Automata (NFA) represent regular languages
concisely, increasing their appeal for applications such as word recognition.
This paper proposes a new approach to generate NFA from an interaction language
such as UML Sequence Diagrams or Message Sequence Charts. Via an operational
semantics, we generate a NFA from a set of interactions reachable using the
associated execution relation. In addition, by applying simplifications on
reachable interactions to merge them, it is possible to obtain reduced NFA
without relying on costly NFA reduction techniques. Experimental results
regarding NFA generation and their application in trace analysis are also
presented.
