STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES
Filippo Mignosi · International Journal of Foundations of Computer Science · 1990
If x is a rational number, 0 c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.