Counting-strings Counting Strings - Part 2
Post
Cancel

Counting Strings - Part 2

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

Now, let’s define the same for regular expressions. And then the fun begins

Given a Regular language \(R\), Minimal Regular Expression is the regular expression generated from the minimal DFA that accepts \(R\)

For example:
Let \(R_0 = (a+b+ab)^\ast, R_1 = (a+b)^\ast \).
\(R_0\) is not Minimal since we have two distinct ways of accepting the string \(ab\). But \(R_1\) is Minimal

Let \([R]_n \) denote the number of n length strings accepted by the minimal regular expression \(R\)

The following definitions are valid for all Minimal Regular Expression

Defn. 1

\(R = \alpha \)

then, \([R]_n = \begin{cases} 1 &\text{if n = $\vert\alpha\vert$ } \\ 0 &\text{otherwise} \end{cases} \tag{1}\)

Proof.: This is the base case. \(R\) accepts \(\alpha\). So, there is only one string of length \(n \) generated, i.e., \(\alpha\)

Defn. 2

\(R = R_1 + R_2 \)

then,

\[[R]_n = [R_1]_n + [R_2]_n \tag{2}\]

Proof.: By defination \(R_1\) and \(R_2\) there will be no common prefix except \(\epsilon\), so \(R_1\) and \(R_2\) generate different strings

Defn. 3

\(R = R_1 \cdot R_2 \)

then,

\[[R]_n = \sum_{\substack{0 \leq k \leq n}}{[R_1]_k \cdot [R_2]_{n-k}} \tag{3}\]

Proof.: Let \(s\) be one of the strings accepted by \(R\). Since \(R = R_1 \cdot R_2 \), we can generate \(s[:k]\) from \(R_1\) and \(s[k:]\) from \(R_2\), where \( 0 \leq k \leq n \).
Let \(k’\) be a value of \(k\) such that \(s[:k]\) is not accepted by \(R_1\) then \([R_1]k\) will be 0 \(\implies [R_1]{k’} \cdot [R_2]_{n-{k’}} = 0\). In other words, \(k’\) does not contribute to \([R]_n\)

Defn. 4

\(R = {R}^\ast \)

then,

\[[R^\ast]_n = \begin{cases} 1 &\text{if n = 0 } \\ \sum_{\substack{1 \leq k \leq n}}{[R]_k \cdot [R^\ast]_{n-k}} &\text{n} \geq 1 \end{cases} \tag{4}\]

Proof.:
From the defination, \(R^\ast = \epsilon + R + R^2 + R^3 + \dots = \epsilon + R \cdot R^\ast \).
Applying (1) for \(n = 0\), and (3) for \(n \geq 1\) we get the result.

Example 1.

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

Let \(R = a+bb+ccc \)
From (4),

\[[R^\ast]_n = [R]_1 \cdot [R^\ast]_{n-1} + \dots + [R]_{n-1} \cdot [R^\ast]_{1}\]

For \(n \geq 4\), \([R]_n = 0\) since the maximum string length generated by \(R\) is \(3\).

So,
\([R^\ast]_n = [R]_1 \cdot [R^\ast]_{n-1} + [R]_2 \cdot [R^\ast]_{n-2} + [R]_3 \cdot [R^\ast]_{n-3} \tag{eg.1.1}\)

Using (1), we have \([R]_1 = 1, [R]_2 = 1, [R]_3 = 1\)

Substituting the values in (eg.1.1), we get,

\[\begin{align} [R^\ast]_n &= 1 \cdot [R^\ast]_{n-1} + 1 \cdot [R^\ast]_{n-2} + 1 \cdot [R^\ast]_{n-3} \\ &= [R^\ast]_{n-1} + [R^\ast]_{n-2} + [R^\ast]_{n-3} \end{align} \tag{eg.1.2}\]

Base Cases:

\[\begin{align} [R^\ast]_0 &= 1 \\ [R^\ast]_1 &= 1 \\ [R^\ast]_2 &= 1+1 = 2 \\ \end{align}\]

So, the solution is

\[[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}\]

Example 2.

Find the recurrence for the number of strings accepted by \({(a+bb+cc+ddd)}^\ast\)

Let \(R = a+bb+cc+ddd \)
From (4),

\[\begin{align} [R^\ast]_n &= [R]_1 \cdot [R^\ast]_{n-1} \\ &+ [R]_2 \cdot [R^\ast]_{n-2} \\ &+ [R]_3 \cdot [R^\ast]_{n-3} \\ &+ \dots \\ &+ [R]_{n-2} \cdot [R^\ast]_{2} \\ &+ [R]_{n-1} \cdot [R^\ast]_{1} \end{align}\]

For \(n \geq 4\), \([R]_n = 0\) since the maximum string length generated by \(R\) is \(3\).

So, \([R^\ast]_n = [R]_1 \cdot [R^\ast]_{n-1} + [R]_2 \cdot [R^\ast]_{n-2} + [R]_3 \cdot [R^\ast]_{n-3} \tag{eg.2.1}\)

Using (1), we have \([R]_1 = 1, [R]_2 = 2, [R]_3 = 1\)

Substituting the values in (eg.2.1), we get,

\[\begin{align} [R^\ast]_n &= 1 \cdot [R^\ast]_{n-1} + 2 \cdot [R^\ast]_{n-2} + 1 \cdot [R^\ast]_{n-3} \\ &= [R^\ast]_{n-1} + 2 \cdot [R^\ast]_{n-2} + [R^\ast]_{n-3} \end{align} \tag{eg.1.2}\]

Base Cases:

\[\begin{align} [R^\ast]_0 &= 1 \\ [R^\ast]_1 &= 1 \\ [R^\ast]_2 &= 1+1+1 = 3 \end{align}\]

So, the solution is

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

That’s all for part-2. Stay tuned for the next part :)

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