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

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.

• You can show that it is not regular by looking at the Myhill-Nerode classes of the words $(ab)^k$, for $k=1,2,...$. Observe that if $x=(ab)^m$ and $y=(ab)^n$, with $m>n$, then taking $z=(ba)^n$ we get that $yz$ is contractable, and $xz$ it not. So, the classes of $(ab)^k$ are all different and there are infinitely many of them.
– plop
Mar 9 at 15:07
– D.W.
Mar 9 at 20:08
• Please credit the original source of all copied material. See cs.stackexchange.com/help/referencing
– D.W.
Mar 9 at 20:08

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$$.

• @EmilJeřábek. Ooops I've written my grammar thinking that a contraction can only happen for strings of at least three identical consecutive characters (and not two!). I've fixed that. Mar 9 at 18:04
• Your analysis sounds correct, but I’m beginning to think that the restriction in the OP that contractions can only be applied to maximal-length sequences of consecutive symbols is actually immaterial (if the word is contractible without this restriction, we can reorder and combine the contractions to satisfy the extra requirement). If true, this can be used to simplify the grammar: I believe that the same language is generated by just $S\to\varepsilon\mid(aS)^{\ge2}\mid(bS)^{\ge2}$ (that is, formally: $S\to\varepsilon\mid AA\mid BB$; $A\to aS\mid AA$; $B\to bS\mid BB$). Mar 9 at 19:08
• @Steven I would like to see your response to Emil's comment before I upvote. I am following this answer. Mar 10 at 6:02
• @JohnL. My comment is just an additional thought. You should upvote the answer regardless of it. Mar 10 at 9:09