I have a state machine where from each state you can only go to one other state. Furthermore, there is also a cost associated with certain state transitions (these costs are always $ \geq 0$ which means sometimes $0$).
I want to basically answer the question "If you start in an arbitrary state and proceeded $t$ steps in time, where $t$ is large, what is the total cost you'd incur along the way?"
For large $t$ the best approach I can think of is matrix exponentiation, but I do not know how to set up this sort of cost + state machine. For example consider something easy like this where I have two matrices for both the pathways and the costs (since sometimes the cost may be $0$):
Pathway matrix = $\begin{pmatrix} 0 & 1 \\ 0 & 1\end{pmatrix}$
Cost matrix = $\begin{pmatrix} 0 & 0 \\ 0 & 5\end{pmatrix}$
What this says is "From state $0$ you can go to state $1$, and from state $1$ you can go to state $1$. A cost of $5$ is incurred if you move from state $1$ to $1$."
So for example if $t=1000$ and I start in state $0$, I should incur a cost of $5(t-1) = 4995$. In practice these matrices would be more complicated than this but I'm using something simple for illustration.
How would I set up such a system so I can exponentiate and get the result of the total cost from a given state after $t$ steps?
Since you are talking about costs, I assume you want to minimise them. You could use the $\min$-plus semiring $(\mathbb{R} \cup \{+ \infty\}, \min, +)$, in which the addition is $\min$ and the multiplication is $+$, to represent your data in a single matrix:
$$\begin{pmatrix} \infty & 0 \\ \infty & 5\end{pmatrix}$$
Here $\infty$ means no transition and $0$ means a transition with cost $0$. If you take the square and the cube of this matrix, you will get $$ \begin{pmatrix} \infty & 0 \\ \infty & 5\end{pmatrix}\begin{pmatrix} \infty & 0 \\ \infty & 5\end{pmatrix} = \begin{pmatrix} \infty & 5 \\ \infty & 10 \end{pmatrix} \qquad \begin{pmatrix} \infty & 5 \\ \infty & 10\end{pmatrix}\begin{pmatrix} \infty & 0 \\ \infty & 5\end{pmatrix} = \begin{pmatrix} \infty & 10 \\ \infty & 15\end{pmatrix} $$ since, for instance, $\min\{\infty+ 0, 0+ 5\} = \min\{\infty, 5\} = 5$ and $\min\{\infty+ 0, 5+ 5\} = \min\{\infty, 10\} = 10$. More generally, you would get by induction $$ \begin{pmatrix} \infty & 0 \\ \infty & 5\end{pmatrix}^t = \begin{pmatrix} \infty & 5(t-1) \\ \infty & 5t\end{pmatrix} $$ and hence a path of length $t$ from $0$ to $1$ will have cost $5(t-1)$.