A lower-bound for the number of productions required for a certain class of languages

AbstractW. Bucher, K. Culik II, H. Maurer and D. Wotschke (Theoretical Computer Science 14(1981), pp. 227–246) posed the problem of producing the language Ln = {ab: 1≤a,b≤n and a≠b} with a minimal number of productions. Later, W. Bucher, K. Culik II and H. Maurer showed that 2n + O(n12) productions are sufficient. In this note we show that 2n + ⌈2n12⌉ productions are necessary for all n≥ 6