UBC Theses and Dissertations

UBC Theses Logo

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