This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the perspective of inductive learning. The motivation to ask this question comes from reading some of Solomonoff's papers on algorithmic probability and resource bounded probability.
In Solomonoff's algorithmic probability, one studies induction / machine learning under the assumption that all observed data is the output of a universal Turing machine with random input. With this prior, expectation maximization via Bayesian methods leads to the natural notion that the best model for a particular observed sequence of data is the one generated by the shortest program (aka minimum description length / Kolmogorov complexity).
One cute thing about this prior is that it beats the so-called "no free lunch theorems" as best as possible. Because Kolmogorov complexity is unique up to an additive constant across Turing machines, as long as the underlying sequence is non-uniformly random it can at least theoretically be learned given a finite number of samples.
The bad thing of course is that Kolmogorov complexity is uncomputable, so this is really more of a theoretical curiosity than an actual tool for machine learning. To get around this, Solomonoff proposed the notion of resource bounded probability, where the resources for the Turing machine are ultimately limited (ie bounded compute time/space). In the case of a space bound, this limitation ultimately transforms the Turing machines into DFAs, which leads to my question:
Given the algorithmic prior (ie observed data is generated by some universal Turing machine fed uniform random inputs), what is the probability that the data observed is the output of a DFA?
Of course if it is a DFA, life is really great since there are a bunch of tricks out there for estimating such a DFA. Also it might be interesting to maybe look at other classes of automata as means to get other variants of resource limited types of results.
Best Answer
The set of possible answers to this question is a countable dense subset of (0,1), because it depends on your choice of universal Turing machine.