Consider $S$ the following recursively defined set; $S$ contains the empty string and, for any strings $a$ and $b$ in $S$, the string $(a b)$ is also in $S$. Here are the first few elements of $S$ : $$ (),(()),((())),(()()),(((()))),((()))),,((()))),(()(())) \ldots $$ The weight $w(s)$ of a non-empty string $s$ is $n-1$ where $n$ is the number of ('s. Let $T$ be the set of non-empty strings of $S$. Following the methods which means without explicitly finding the recurrence, prove that $$ 1+(x-1) M(x)+x^2 M(x)^2=0 $$ where $M(x)$ is the generating function of $T$ with the given weight function. [Hint: does this weight function meet the requirement to be the weight function of a language? If not, one needs to define an auxiliary weight function.]
I think we must use this: The weight $w(s)$ of a non-empty string $s$ in $T$ is defined as $n-1$, where $n$ is the number of occurrences of '(' in $s$. This effectively counts the number of pairs of parentheses, as each '(' is matched with a corresponding ')'. Given the recursive definition of $S$, a string in $T$ can be seen as being constructed from smaller strings in $T$, enclosed within a pair of parentheses.
Based on the recursive structure, we can express the generating function $M(x)$ in terms of itself. Considering a non-empty string $s=(a b)$ in $T$, where $a$ and $b$ are also from $T$, we see:
- The empty string contributes nothing to $T$, hence it does not appear in $M(x)$.
- The weight contribution of a single pair of parentheses is $x$, as it adds one to the number of '(' characters.
- A string formed by enclosing a smaller string from $T$ within parentheses contributes $x M(x)$ to the generating function, accounting for the additional pair of parentheses.
- Since a string in $T$ can be formed by concatenating two strings from $T$ and enclosing them in parentheses, we get an additional contribution of $x^2 M(x)^2$.
I don't really know how to give a formal proof. I would appreciate some help.
What you would like to show is equivalent to proving that $M(x) = 1 + xM(x) + x^{2}M(x)$. Thus, you would want to find some expression for the set $T$ in terms of itself from which you can obtain the desired expression for $M(x)$. To do this we look at how strings of $T$ can be formed, similar to the remarks you made about strings in $T$ and their contributions to $M(x)$.
Consider the set $T$. The string $()$ has weight $0$. As you said, if we have a string $x \in T$ then clearly $(x) \in T$. If $y \in T$ is another string in $T$, then an additional string in $T$ can be made by enclosing the concatenation $(x)y$ of $(x)$ and $y$ in parentheses: $((x)y) \in T$.
On the other hand, let $(x), ((x)y) \in T$. Then clearly $x$ is either $()$ or another string in $T$. The same holds for $y$. Note that we account for the strings you have listed. For example, we account for $(())$ and $(()(()))$.
We obtain an expression $T = () + (T) + ((T)T)$. To proceed we define an auxiliary weight function $w$ where $w(x)$ for $x \in T$ equals the number of open parentheses in $x$. If we write $1$ for $($ and $0$ for $)$, the weight of a string is the number of $1$'s. Finally, we have the following (where we make use of product and sum identities of generating functions):
\begin{align*} & \Phi(T) = \Phi(10) + \Phi(1T0) + \Phi(11T0T0) \\\\ & = 1 + x\Phi(T) + x^{2}\Phi(T) = 1 + xM(x) + x^{2}M(x). \end{align*}