# Prefix Probability in Stochastic Languages

I was reading the following paper (http://aclweb.org/anthology/W/W13/W13-1801.pdf) and they state that, given a Probabilistic Finite Automata $A$ and a string $w$, finding the probability $Pr_A(w\Sigma^*)$ is simple (section 3, property 3. Just before the start of section 4). However, this isn't immediately clear to me since, even using some dynamic programming approach, you may have to compute the probability of an infinite number of paths (since it is not acyclic) starting at all of the states that are the last state reached in a path, $\Theta$, that generates $w$.

I was not able to find an answer in the references of that paper or any relevant papers on the subject.

To summarize, I am looking for an algorithm that, given a PFA $A$ and a string $w \in \Sigma^*$, returns the probability $Pr_A(w\Sigma^*)$. in other words, the probability of any string having $w$ as a prefix.

Thanks in advance.

## 1 Answer

According to their definition of PFA, to compute $Pr(w\Sigma^*)$ you simply need to compute the probability of having read $w$ after a random path of length $|w|$, which is easy.

Their model of PFA differs from the usual model: usually, for each state $q$ and letter $a$, we have $\sum_{q'} \delta(q,a,q')=1$, so you assume that in a run, the word is fixed beforehand and probabilities are played upon reading each letter.

Here, the setting is different: for each state $q$, we have $F(q)+\sum_{a,q'} \delta(q,a,q')=1$, meaning that a path is chosen at random (including the end), and induces a word. That is what makes the problem easier.