Open Collections

Turkmenafsar, Serdar

University of British Columbia

Let Tn be a uniformly randomly selected word of size n from an irreducible unambiguous context-free grammar $H$. We analyze the number of times of seeing a fixed pattern within Tn by constructing a critical multitype branching process (on the context free grammar) that assigns the same probability to words of the same size (if the grammar is regular, then we construct such a Markov chain instead). We give an easy way to compute the density constants of expectations for any given pattern. We also give a lower bound for the density constant of the variance in the case that the given pattern is replaceable by another pattern. Using fringe convergence results from Stufler's paper, we show that a uniformly selected fringe subtree from a uniformly selected derivation tree converges to the unconditioned branching process.

Text

2021-05-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/78169

Mathematics

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/