how do I parenthesize the product of abcdef??

Question

This is about catalan number and parenthesizing.

a)Determine the list of five 1's and five 0's that corresponds to each of these:

1. (((ab)c)(d(ef))) = (what I did: 1110010110)

2. (a(b(c(d(ef)))))) = (what I did: 1010101010)

   3.((((ab)(cd))e)f) = (what I did: 1111001100)

b) find the way to parenthesize abcdef that corresponds to each given list of five 1's and five 0's

1. 1110010100 = (what I did: (((ab(c(de)f)
2. 1100110010 = (what I did: ((ab((cd)(e)f)
3. 1011100100 = (what I did: (a(((bc)(ef))

Did I do it correct? I seem to understand a bit but then I'm confused again. Anyone can please clarify this ??

Answer 1

Question a)

1. A letter is replaced by the empty word $\epsilon$
2. An expression (XY) is replace by the word $\color{red}{1}u_x\color{blue}{0}u_y$ where $u_x$ is the word for $X$ and $u_y$ is the word for $Y$.

I add colors to understand where is the $1$ and the $0$ added at this step.

Example : (((ab)c)(d(ef)))

• (ab) is $\color{red}{1}\color{blue}{0}$
• ((ab)c) is $\color{red}{1}10\color{blue}{0}$
• (ef) is $\color{red}{1}\color{blue}{0}$
• (d(ef)) is $\color{red}{1}\color{blue}{0}10$
• (((ab)c)(d(ef))) is $\color{red}{1}1100\color{blue}{0}1010$

Question b)

This is the inverse computation.

1. An empty word is replaced by a letter
2. In a word $w$ find the first (leftmost) $0$ such that $w=\color{red}{1}u_x\color{blue}{0}u_y$ and $u_x$ contains the same number of $0$'s and $1$'s. Then replace by $(XY)$ where $u_x$ is the word for $X$ and $u_y$ is the word for $Y$

Example : $1110010100$ ($x$ is any letter)

• $\color{red}{1}11001010\color{blue}{0}$ will be cut into $11001010$ and $\epsilon$
• $\color{red}{1}10\color{blue}{0}1010$ will be cut into $10$ and $1010$
• $\color{red}{1}\color{blue}{0}$ will be cut into $\epsilon$ and $\epsilon$
• $\color{red}{1}\color{blue}{0}10$ will be cut into $\epsilon$ and $10$

So now

• $10$ is $(xx)$
• $1010$ is $(x(xx))$
• $11001010$ is $((xx)(x(xx))$
• $1110010100$ is $(((xx)(x(xx))x)$

Then replace $x$ by appropriate letters and $1110010100$ is $(((ab)(c(de))f)$