In this paper we present an information theoretic measure for the unsupervised inference of Probabilistic Recursive Transition Networks and Probabilistic Finite State Automata from bodies of training data. The method we present here is based on the Minimum Message Length principle. It constructs a compact code or message which contains a trial theory (automaton) about the data followed by the data encoded using the theory. The trial theory with the shortest message length (including the data) contains the most likely explanation theory about the data among all the trial theories. We do not present an algorithm for generating the trial theories as it may vary depending on the domain of the problem.