Counterexample to a recursive matched parenthesis proposition.

Question

I am attempting problem 7.28 of Discrete Mathematics notes from MIT OCW. Link to problem

---

Definitions: All recursively defined

• RecMatch (RM):
  • Base Case: $\lambda \in RM$ [$\lambda$ is empty string]
  • Constructor Case: $s,t \in RM \implies \color{red}[s\color{blue}]t \in RM$
  • Eg.: $\color{red}[\lambda\color{blue}]\lambda = \color{red}[\color{blue}] \in RM \ and \ \color{red}{[[}\color{blue}{]]}\color{red}[\color{blue}] \in RM$
• Arithmetic Expression (AE):
  • Base Case:
    • (a.) $x \in AE$ where $x$ is the only variable allowed
    • (b.) $k \in AE$ where $k \in \mathbb{Z^+}$
  • Constructor Case: Let $a,b \in AE$; then
    • $\color{red}[a + b\color{blue}] \in AE$
    • $\color{red}[a * b\color{blue}] \in AE$
    • $-\color{red}[a\color{blue}] \in AE$
  • Eg.:
    • $3x^2 + 2x + 1 = \color{red}{[[}3 * \color{red}[x * x\color{blue}{]]}+\color{red}{[[}2*x\color{blue}]+1\color{blue}{]]} \in AE$
    • $x(x-1) = \color{red}[x * \color{red}[x +-\color{red} [1\color{blue}{]]]}\in AE$
• erase($e$): erases the symbols in $e$ where $e \in AE$. So erase($\color{red}{[[}3 * \color{red}[x * x\color{blue}{]]}+\color{red}{[[}2*x\color{blue}]+1\color{blue}{]]}$ = $\color{red}{[[[}\color{blue}{]]}\color{red}{[[}\color{blue}{]]]}$)

---

Problem: Give an example of a small string $s \in RM$ such that $\color{red}[s\color{blue}] \neq erase(e)\ \text{for any}\ e\in AE$

I have tried many strings $s \in RM$ like $\lambda, \color{red}{[}\color{blue}], \color{red}{[[}\color{blue}{]]}\ \text{and}\ \color{red}[\color{blue}]\color{red}[\color{blue}]$ but for all these I can come up with an $e \in AE$ so that $\color{red}[s\color{blue}] = erase(e).$

Could anyone give me a hint so that I could solve this?

Answer 1

I have solved the question and now posting my solution.

$s = \color{red}[\color{blue}]\color{red}[\color{blue}]\color{red}[\color{blue}] \in RM\ \text{such that}\ \color{red}[s\color{blue}] \neq erase(e)\ \text{for any}\ e \in AE$ since only two arithmetic expressions can be used to make a new arithmetic expressions. For three matched brackets to occur simultaneously, three AEs must be used to then form a single AE which is not allowed.