A word is formed by starting with "$0$" and then adding "$1$" either to the start or to the end i.e we can form "$10$" or "$01$". In the next step we add a "$0$", again either to the start or to the end. This is continued, alternating the symbol we add.
Denote by $L_n$ the language containing all words of length $n$ that can be formed like this. We can define this recursively:
$$L_0 = \{""\}$$ $$L_n = \{c+w \space | \space w\in L_{n-1}\} \cup \{ w+c \space | \space w\in L_{n-1} \},$$ $$ \text{where } c="0" \text{ if } n \text{ is odd and } c="1" \text{ if } n \text{ is even }$$ $$\text{and + means the concatenation of strings.}$$
We get:
$L_0 = [""]$ (the empty string)
$L_1 = ["0"]$
$L_2 = ["10", "01"]$
$L_3 = ["010", "100", "001"]$
$L_4 = ["1010", "0101", "1100", "1001", "0011"]$
$L_5 = ["01010", "10100", "00101", "01100", "11000", "01001", "10010", "00011", "00110"]$
$L_6 = ["101010", "010101", "110100", "101001", "100101", "001011", "101100", "011001", "111000", "110001", "010011", "110010", "100011", "000111", "100110", "001101"]$
Denote $a_n = \# L_n$. These start out as $$[1, 1, 2, 3, 5, 9, 16, 29, 52, 94, 170, 308, 560, 1018, 1856, 3383, 6177, 11279, 20614, 37685, 68926, 126112, 230802, 422557, 773730, 1417222, \dots]$$
Questions:
- Is there a context free grammar for the language $L=\bigcup L_n$?
- Is there a formula for $a_n$, or what is their generating function?
- I noticed that $\frac{a_n}{a_{n-1}}$ seems to approach something like $1.832...$. Is this true and what is this constant? It's like the factor "how many different words" each word from $L_{n-1}$ produces to $L_n$ (each produces two, but some of these are same as others).
Numerical experimentation suggests that the generating function has a simple pole at about 0.544938, so that the ratios should go to 1.83507 or so.