Find a language which needs for Jaffe’s Matching Pumping Lemma at least constant \(k = 100\) and can be recognised by a deterministic finite automaton with \(100\) states. Prove your answer.
Let \(\Sigma = \left\{0\right\}\) (doesn’t matter much here), and let \(L = \left\{w\in\Sigma^*: \left\lvert w\right\rvert \text{ is a multiple of }100\right\}\). \(L\) can be recognised by a dfa with \(100\) states, specifically one where the state corresponds to number of characters read modulo 100, and accepts when it is \(0\).
\(L\) satisfies Jaffe’s Matching Pumping Lemma with \(k = 100\). To see why, fix any \(x\in \Sigma^*\) and \(y \in \Sigma^{100}\) and it is easy to see that for any \(h\in\mathbb{N}\), \(L_{xy} = L_{xy^h} = \left\{w\in\Sigma^*: \left\lvert w\right\rvert + \left\lvert x\right\rvert \text{ is a multiple of }100\right\}\).
Suppose \(L\) satisfies Jaffe’s Matching Pumping Lemma with \(k < 100\), then there exists \(y\in\Sigma^k\) such that for all \(h\in\mathbb{N}\), \(L_{y^h} = L\) so in particular \(L_y = L\), but \(\left\lvert y\right\rvert < 100\) so \(0^{100-\left\lvert y\right\rvert} \in L_y\) but clearly is not in \(L\).