1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – plop Mar 9 at 15:07
  • $\begingroup$ You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 9 at 20:08
  • 3
    $\begingroup$ Please credit the original source of all copied material. See cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Mar 9 at 20:08
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$ – Steven Mar 9 at 18:04
  • $\begingroup$ 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$). $\endgroup$ – Emil Jeřábek Mar 9 at 19:08
  • $\begingroup$ @Steven I would like to see your response to Emil's comment before I upvote. I am following this answer. $\endgroup$ – John L. Mar 10 at 6:02
  • $\begingroup$ @JohnL. My comment is just an additional thought. You should upvote the answer regardless of it. $\endgroup$ – Emil Jeřábek Mar 10 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.