Stochastic Context-Free Grammars

The probabilistic aspect is introduced into syntactic recognition tasks via Stochastic Context-Free Grammars. A Stochastic Context-Free Grammar (SCFG) is a probabilistic extension of a Context-Free Grammar. The extension is implemented by adding a probability measure to every production rule:

$$\begin{array}{lr} A \rightarrow \lambda & [p] \end{array}$$

The rule probability p is usually written as $P(A \rightarrow \lambda)$. This probability is a conditional probability of the production being chosen, given that non-terminal A is up for expansion (in generative terms). Saying that stochastic grammar is context-free essentially means that the rules are conditionally independent and, therefore, the probability of the complete derivation of a string is just a product of the probabilities of rules participating in the derivation.

Given a SCFG G, let us list some basic definitions:

.

The probability of partial derivation $\nu \Rightarrow \mu \Rightarrow \dots \lambda$ is defined in inductive manner as

)

$P(\nu) = 1$

)

$P(\nu \Rightarrow \mu \Rightarrow \dots \lambda) = P(A \rightarrow \omega)P(\mu \Rightarrow \dots \lambda)$, where production $A \rightarrow \omega$ is a production of G, $\mu$ is derived from $\nu$ by replacing one occurrence of A with $\omega$, and $\nu, \mu, \dots, \lambda \in V_{G}^{*}$.

.

The string probability $P(A \Rightarrow^{*} \lambda)$ (Probability of $\lambda$ given A) is the sum of all left-most derivations $A \Rightarrow \dots \Rightarrow \lambda$.

.

The sentence probability $P(S \Rightarrow^{*} \lambda)$ (Probability of $\lambda$ given G) is the string probability given the axiom S of G. In other words, it is $P(\lambda \vert G)$.

.

The prefix probability $P(S \Rightarrow_{L}^{*} \lambda)$ is the sum of the strings having $\lambda$ as a prefix,

$$P(S \Rightarrow_{L}^{*} \lambda) = \sum_{\omega \in V_{G}^{*}} {P(A \Rightarrow^{*} \lambda \omega)}$$

In particular, $P(S \Rightarrow_{L}^{*} \epsilon) = 1$.