6. Singularity Analysis of Generating Functions
VI.1 A glimpse of basic singularity analysis theory
VI.2 Coefficient asymptotics for the standard scale
VI.4 The process of singularity analysis
VI.5 Multiple singularities
VI.6 Intermezzo: functions amenable to singularity analysis
VI.7 Inverse functions
VI.9 Functional composition
VI.10 Closure properties
VI.11 Tauberian theory and Darboux’s method
VI.1Use the standard function scale to directly derive an asymptotic expression for the number of strings in this following CFG: S = E + U×Z×S + D×Z×S, U = Z + U×U×Z, D = Z + D×D×Z.
VI.2Give an asymptotic expression for the number of rooted ordered trees for which every node has 0, 2, or 3 children. How many bits are necessary to represent such a tree?
Program VI.1In the style of the plots in Lecture 6, do $r$- and $\theta$-plots of $1/\Gamma(z)$ in the unit square of size 10 centered at the origin (see Program IV.2)