부산대학교 도서관

The rational index of a nonempty language $L$ is the function $\rho_n\colon\bold N_+\to\bold N$ defined by $$ \rho_L(n)=\max\{\min\{|w|;w\in L\cap K\};\ L\cap K\neq\varnothing,\ K\in{\rm REG}_n\}, $$ where ${\rm REG}_n$ is the family of languages recognized by finite automata with at most $n$ states [L. Boasson and M. Nivat, C. R. Acad. Sci. Paris Sér. A-B {\bf 284} (1977), no. 10, A559--A562; MR0428812 (55 \#1832); ibid. Sér. A-B {\bf 284} (1977), no. 11, A625--A628; MR0433991 (55 \#6961); ibid. Sér. A-B {\bf 284} (1977), no. 12, A703--A705; MR0431797 (55 \#4792); Boasson, B. Courcelle and Nivat, SIAM J. Comput. {\bf 10} (1981), no. 2, 284--296; MR0615219 (83b:68078)]. J. Gabarro [``Index rationel, centre et langages algèbriques'', Thèse de 3ème cycle, Univ. Paris VI, Paris, 1981; BullSig(110) 1982:13660] proved that for any positive integer $k$ there are context-free languages with rational index in $\Theta(n^k)$. The authors [Theoret. Comput. Sci. {\bf 57} (1988), no. 2-3, 185--204; MR0960103 (89h:68088)] have proved that there are context-free languages whose rational indexes grow faster than any polynomial and slower than any exponential function $\exp(\lambda\,n)$. Using a similar technique, in the present paper they construct context-free languages whose rational indexes are in $\Theta(n^\lambda)$ for various values of $\lambda>1$, such as the rational numbers, the algebraic numbers and even some transcendental numbers.