부산대학교 도서관

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 finiteautomata 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 arecontext-free languages with rational index in $\Theta(n^k)$. Theauthors [Theoret. Comput. Sci. {\bf 57} (1988), no. 2-3, 185--204;MR0960103 (89h:68088)] have proved that there are context-free languages whoserational indexes grow faster than any polynomial and slower than anyexponential function $\exp(\lambda\,n)$. Using a similar technique, inthe present paper they construct context-free languages whose rationalindexes are in $\Theta(n^\lambda)$ for various values of $\lambda>1$,such as the rational numbers, the algebraic numbers and even sometranscendental numbers.