Find number of occurrences of a character in a string recursively.

Question

Given:

For any symbol a and any string w, let #(a, w) denote the number of occurrences of a in w. For example, #(A, BANANA) = 3 and #(X, FLIBBERTIGIBBET) = 0.

1. Give a formal recursive definition of the function #$ : Σ × Σ^∗ → N$.
2. Prove that #(a, x y) = #(a, x) + #(a, y) for every symbol a and all strings x and y. Your proof must rely on both your answer to part (a) and the formal recursive definition of string concatenation.

For the 1st part I have the following recurrence:

$\text#(a, xy)$

1. 0 if w = empty string
2. 1 if x = $\text{aw}$ or y = $\text{az}$, where both w and z are remaining string.
3. $\text#(a, x) + \text#(a, y)$

I am still stuck on the second one.

I am a self learner and but trying hard to be good in math I found this resource online but this has no solution, please let me know if I am on the right path.

Reference:

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/models/01-strings.pdf

PS: Sorry for the bad formatting but I am not that good in latex.

Answer 1

First of all you need a way to traverse through the string, something like two functions $L$ and $R$ such that for any string $s$ $R(s)$ returns the rightmost character of the string and $L(s)$ returns the string without the rightmost character.

So, for example, if you have a string, let's say "summer", then $R(``summer") = ``r" $ and $L(``summer") = ``summe" $.

Also you need a way (function or predicate) to identify one-character strings, so let's define a set $S$ such that for any $s$, $s\in S$ if and only if $s$ has a single character.

It is not necessary but certainly helpful to define a function $check$ such that for any characters $c_1$ and $c_2$ if $c_1 = c_2$ then $check(c_1, c_2) = 1$, else $check(c_1,c_2) = 0)$.

Once you have these well defined you can define the function $\#$ using recursively using conditional branching, like this:

$$ \forall c \forall s (c \in S \rightarrow \#(c,s) = check(c,R(s)) $$ $$ \forall c \forall s (c \notin S \rightarrow \#(c,s) = \#(c,L(s)) + check(c,R(s))$$

So let me give an example, suppose you want to compute $\#(``a", ``banana")$.

As "banana" is not in $S$ (because it isn't a single character string), then $$\#(``a", ``banana") = \#(``a", L(``banana")) + check(``a", R(``banana"))$$

so as $L(``banana") = ``banan"$ and $R(``banana") = ``a"$ then

$$\#(``a", ``banana") = \#(``a", ``banan") + check(``a", ``a") = \#(``a", ``banan") + 1$$

And then we proceed with this computation:

$$ \#(``a", ``banan") + 1 = \#(``a", ``bana") + check(``a", ``n") + 1 = \#(``a", ``bana") + 1 $$

$$ \#(``a", ``ban") + 1 = \#(``a", ``ban") + check(``a", ``a") + 1 = \#(``a", ``ban") + 2 $$

And so on until we arrive at the last character:

$$ \#(``a", ``b") + 3 = check(``a", ``b") + 3 = 3$$