How to prove the language of contractible strings is context-free but not regular?

Question

How to prove this language is context-free but not regular? I can't figure out it.

A string is contractible if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of consecutive identical symbols.

For example, $abaaababb$ is contractible as witnessed by the following sequence of contractions,
$$ab\underline{aaa}babb \rightarrow abba\underline{bb}\rightarrow a\underline{bb}a \rightarrow \underline{aa}\rightarrow \epsilon$$

Let $L$ be the language of contractible strings over the alphabet ${a, b}$. Prove that $L$ is a context-free language and that $L$ is not a regular language.

Answer 1

For $i \ge 0$ consider the word $x_i = (ab)^i$. For $0 \le i < j$, $(ba)^i$ is a distinguishing extension for $x_i$ and $x_j$. Indeed $x_i(ba)^i \in L$ but $x_j(ba)^i \not\in L$. By the Myhill–Nerode theorem $L$ is not regular.

Given a non-empty word $w \in L$, $w$ can be written as $\alpha_1 \alpha_2 \dots ... \alpha_k$ where (i) each $\alpha_i$ is a non-empty contractible string that starts and ends with the same symbol, and (ii) the first symbol of $\alpha_{i+1}$ differs from the last symbol of $\alpha_i$.

Each $\alpha_i$ starting with some symbol $x$ can be written, in turn, as $x \beta_1 x \beta_2 \dots \beta_h x$, where $h \ge 1$, all $x$ are exactly the characters removed in a single contraction step, and all $\beta_i$ are (possibly empty) substrings that are contracted before contracting $x$. It follows that each non-empty $\beta_i$ must start and end with the unique symbol in $\{a,b\} \setminus \{x\}$.

Consider hen the following context-free grammar $G$, in which $A$ (resp $B$): generates a contractible string starting and ending with $a$ (resp. $b$):$$ S \to \varepsilon \mid S' \mid S''\\ S' \to A \mid AB \mid ABS' \\ S'' \to B \mid BA \mid BAS'' \\ A \to aa \mid aBa \mid aA \mid aBA \\ B \to bb \mid bAb \mid bB \mid bAB $$

The above observations imply that $L(G) \supseteq L$, while a parse tree for $w$ (according to $G$) provides a sequence of contraction for $w$, showing that $L(G) \subseteq L$.