7
$\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$
7
  • 4
    $\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$ Commented Aug 19, 2017 at 15:12
  • $\begingroup$ Assuming your values for $a_n$ are correct, OEIS doesn't find anything. $\endgroup$ Commented Aug 19, 2017 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
    Commented Aug 19, 2017 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$ Commented Aug 20, 2017 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
    Commented Aug 20, 2017 at 22:58

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .