Counting-strings Counting Strings - Part 3
Post
Cancel

Counting Strings - Part 3

I strongly recommend you to read Part-1 and Part-2 before proceeding into this section.

In this part, we will derive a general formula for solving linear recurrences.

Find the recurrence for the number of strings generated by the regular expression \({(a+bb+ccc)}^\ast\)

From Part-2, we have

\[[R^\ast]_n = \begin{cases} [R^\ast]_{n-1} + [R^\ast]_{n-2} + [R^\ast]_{n-3} &\text{n} \geq 3 \\ 1 &\text{n = 0, 1} \\ 2 &\text{n = 2} \end{cases} \tag{eg.1.2}\]

So we have the recurrence \(r_n = r_{n-1}+r_{n-2}+r_{n-3}\) This corresponds to the strings generated by the regular expression \({(a+bb+ccc)}^\ast\)

In other words, \(r_n \) is equal to number of strings of length n generated by \({(a+bb+ccc)}^\ast\). Now suppose we have to construct a string using a, bb, and ccc only

Let’s place ccc \(g_c\) times, bb \(g_b\) times and a \(g_a\) times to make the string. We have,

\[n = 3 g_c + 2 g_b + g_a\]

And, now we place \(g_a\), \(g_b\), and \(g_c\) into groups in

\[ \sum_{\substack{0 \leq g_a, g_b, g_c \leq n}}{\binom{g_a+g_b+g_c}{g_a}\binom{g_b+g_c}{g_b}\binom{g_c}{g_c}} \]

Simplifying,

\[ r_n = \sum_{\substack{0 \leq g_a, g_b, g_c \leq n}}{\frac{(g_a+g_b+g_c)!}{g_a!\space g_b!\space g_c!}} \]

This sums up the article! I hope you had fun :)

This post is licensed under CC BY 4.0 by the author.