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 :)