<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-10T16:15:33.887Z
2017-01-10T16:15:33.887Z
Denis
<p>I was reading the following paper (<a href="http://aclweb.org/anthology/W/W13/W13-1801.pdf" rel="nofollow noreferrer">http://aclweb.org/anthology/W/W13/W13-1801.pdf</a>) 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$.</p>

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

<p>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.</p>

<p>Thanks in advance.</p>

<fl.formal-languages>
Prefix Probability in Stochastic Languages
B Waters
# Prefix Probability in Stochastic Languages

(Asked by: username_0 on 2017-01-08)

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.

**Tags:** fl.formal-languages


---

## 1 answers

### Answer by username_1 on 2017-01-10. Score: 2

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.


---

