TRANSPOSITION GRAMMARS AND PRODUCTION PROBABILITY ESTIMATORS FOR CONTEXT-FREE GRAMMARS (AUTOMATA, STATISTICS, RANDOM WALKS)

This thesis is divided into two major parts.;The second part of the thesis examines production probability estimation. The relative production probabilities of a nonterminal in a probabilistic context-free grammar can sometimes be used to determine the most efficient parse. We shall examine the estimation of production probabilities of probabilistic context-free grammars. This will be done by generating random samples of strings using a probabilistic context-free grammar, and by using ratio estimators to estimate the production probabilities. It is shown that the problem becomes much less complex algebraically by introducing the theory of random walks and showing that a derivation in an n-nonterminal probabilistic context-free grammar is equivalent to an n-dimensional random walk. We also show that the ratio estimators improve as the random sample size increases.;In the first part we construct a transformation on a context-free grammar so that the new language derived by the transformed grammar consists of all strings contained in the original language and, in addition, all strings which can be obtained from any string in the original language by transposing any two adjacent symbols. We prove the correctness of the transposition algorithm and examine the bound on the number of new grammatical productions introduced by the algorithm. After applying this transformation, strings in the new language can be parsed, and any string containing a transposition error can be detected by looking at the productions used in the derivation of that string.