The first chapter of Berstel and Reutenauer's "Noncommutative Rational Series with Applications" presents Schützenberger's theorem that every noncommuting ratio

The first chapter of Berstel and Reutenauer's "Noncommutative Rational Series with Applications" presents Schützenberger's theorem that every noncommuting rational power series is representable, and conversely. The idea is NOT painfully abstract, but makes twenty minutes work of a semester of undergraduate automata theory (an assertion I've tested multiple times in my math office hours). They work with coefficients in an arbitrary semiring, which can be like watching paint dry. However, boolean true/false, and probabilities, make two great examples. The idea that hidden Markov chains is exactly the same theory as CS automata theory is mind-blowing. Once one absorbs this, there's an interesting wrinkle worked out in the 1960's that is still poorly understood. If the outputs are probabilities, do the internal coefficients of the matrices need to be probabilities? Why yes, if we are so enamored with fulfilling our expectations that we can simply draw graphs and label them in understandable ways for people who aren't willing to work very hard or defy expectations. Why no, if one chases the actual math. There are examples that can require arbitrarily many matrix dimensions to model using probabilities, that can be modeled in few dimensions using real numbers outside the [0,1] range. This has a simple explanation. There's a pattern one sees twice, a linear combination with coefficients in [0,1] that sum to one: A probability distribution, and barycentric coordinates. One can have a point cloud of small dimension, whose convex hull requires arbitrarily many vertices. Restricting the coefficients to the [0,1] range means working with these vertices as separate matrix dimensions. Leaving the coefficients unrestricted means working with the raw dimension.