UBC Theses and Dissertations
Patterns in random words of context-free grammars Turkmenafsar, Serdar
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.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International