On the number of words in the language {w ε σ∗ ∣ w = wR}2

✍ Scribed by R. Kemp

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 659 KB
• Volume: 40
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90123-6

✦ Synopsis

Let S be the set of all palindromes over B *. It is well known. that the language S* is an ultralinear, inherently ambiguous context-free language. In this paper we derive an explicit expression for the number of words of length n in S2. Furthermore, we show, that for card(P)> 1 the asymptotical density of the language S* is zero and that, in the average, each word w of ien_gth n in S2 has exactly one factorization into two palindromes for large n; the variance is zero for large n. Finally, we compute an expression for the structure-generatingfunction T(S2; L) of the language S*; it remains the open problem, if TCS'; z) is a transcendental or an algebraic function.