2 problems

Let $\tau_{\rm sync}$ denote the synchronization time of the random DFA, and retain the notation in which $\mathbf Q$ is the uniform distribution on words of the relevant length. R…

Let $(V,\mathcal C,\{f_x\}_{x\in V})$ be a random DFA with $|V|=n$. For a fixed $t\in\mathbb N$, let $\mathbf Q=\mathbf Q_t$ be the uniform distribution over words in…