# Language formed by adding symbols to start or end turn by turn

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).
• For the first question: Yes, of course. The process you describe $L$ by directly corresponds to a context-free grammar: $$A\to \varepsilon \mid 1B \mid B1 \qquad B\to 0A \mid A0 \qquad S \to A \mid B$$ – Henning Makholm Aug 19 '17 at 15:12
• Assuming your values for $a_n$ are correct, OEIS doesn't find anything. – Henning Makholm Aug 19 '17 at 15:18
• @HenningMakholm I thought about something like that but had and still have some trouble seeing it because "the symbol could end up in the middle". But I'm beginning to believe it : ). Yes I also tried OEIS. Upto $94$ it finds something but not after that. If someone want's to also check the values, we'd have more confirmation. – ploosu2 Aug 19 '17 at 15:29
• The values check out, and the next one is 2596086. A Hankel matrix formed from these first 27 entries has a non-zero determinant. Therefore there is no linear recurrence of order 14 or less. – Peter Taylor Aug 20 '17 at 16:33
• We can see the strings as binary numbers, maybe that helps. The Mathematica code to generate $a_n$ becomes: add[list_, i_] := If[EvenQ[i], Union[list, 2 list], Union[2^i + list, 2 list + 1]]; Length /@ FoldList[add, {0}, Range] – Paul Aug 20 '17 at 22:58

## 1 Answer

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.