Determinization

An $\epsilon$-free pfsr is deterministic if there is a single start state, and if for all states $q\in Q$ and symbols $\sigma\in\Sigma$ there is at most one transition $(q,\pi,q')$ such that $\pi(\sigma)$. If a pfsr M is deterministic then checking whether a given string w is accepted by M can be implemented efficiently: linear in w, and independent on the size of M.

A determinization algorithm [2,13,14] maintains subsets of states. Each subset is a state in the deterministic machine. To compute the transitions leaving a given subset D, a determinization algorithm computes for each symbol $\sigma\in\Sigma$ the set of states Q such that $p\in D, q\in Q$ and $(p,\sigma,q)\in E$.

In the case of predicates, however, transitions might overlap. For example, one transition may be applicable for high vowels, whereas another transition may be applicable for round vowels. In the determinized pfsr, such overlaps are not allowed. Therefore, we create a separate transition for high and round vowels, another transition for vowels which are high but not round, and a third transition for vowels which are round but not high.

In general, in order to compute the transitions leaving a given subset D we do as follows. Firstly we compute the function Trans^D: $\Pi\rightarrow 2^Q$, defined as: $\mbox{\it Trans}^D(\pi) = \{q\in Q\vert p\in D, (p,\pi,q)\in E\}$. For example, suppose D={p}, and suppose we have transitions

$$E=\{\begin{array}[t]{l}(p,\pi_1,q_1),(p,\pi_1,q_2),(p,\pi_2,q... ..._3),\\ (p,\pi_2,q_4),(p,\pi_3,q_3),(p,\pi_3,q_5)\}\end{array}$$

In that case:

$$\mbox{\it Trans}^D(\pi_1) =\{q_1,q_2\}, \mbox{\it Trans}^D(\pi_2) =\{q_2,q_3,q_4\}, \mbox{\it Trans}^D(\pi_3) =\{q_3,q_5\}$$

Let $\Pi'$ be the predicates in the domain of Trans^D. For each split of $\Pi'$ into two subsets $\pi_1\dots \pi_i$ and $\pi_{i+1}\dots\pi_n$ we have a transition:

$$(D,\pi_1\wedge\dots\wedge\pi_i\wedge\neg\pi_{i+1}\wedge\dots\... ...box{\it Trans}^D(\pi_1)\cup\dots\cup\mbox{\it Trans}^D(\pi_i))$$

for the example we obtain the transitions:⁴

$$\begin{array}{ccccc} ( & D, &\pi_1\wedge\pi_2\wedge\pi_3, &\... ...pi_1\wedge\neg\pi_2\wedge\neg\pi_3, &\emptyset&)\\ \end{array}$$