4
$\begingroup$

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).
$\endgroup$
  • 3
    $\begingroup$ 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 $$ $\endgroup$ – Henning Makholm Aug 19 '17 at 15:12
  • $\begingroup$ Assuming your values for $a_n$ are correct, OEIS doesn't find anything. $\endgroup$ – Henning Makholm Aug 19 '17 at 15:18
  • $\begingroup$ @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. $\endgroup$ – ploosu2 Aug 19 '17 at 15:29
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Aug 20 '17 at 16:33
  • $\begingroup$ 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[30]] $\endgroup$ – Paul Aug 20 '17 at 22:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.