1
$\begingroup$

This question already has an answer here:

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$

I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and prove. The word itself $ww$ above the alphabet $a, b$ is not context-free, but here we have $(a + b) ^ {*}$ before and after, and it changes a lot, I think.

Is it possible to describe this language with a regular expression? For example $$(a + b) ^ {*} (aa + bb + abab + baba) (a + b) ^ {*}$$ So is the language regular?

$\endgroup$

marked as duplicate by Apass.Jack, Yuval Filmus, Evil, xskxzr, David Richerby Feb 12 at 11:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

A word is square-free if it contains no non-empty sub word of the form $y^2$. Your language consists of all words over $\{a,b\}$ which are not square-free. It is not difficult to enumerate (using exhaustive search) all square-free words over $\{a,b\}$: $$ \epsilon, a, b, ab, ba, aba, bab. $$ Since this list is finite, the language of square-free words over $\{a,b\}$ is trivially regular, and so is its complement.

In contrast, the language of square-free words over $\{a,b,c\}$ is not regular. This follows from the existence of an infinite square-free word $w$, which can be obtained from the Thue–Morse sequence.

Indeed, I claim that the set of prefixes of $w$ is pairwise inequivalent modulo your language. To see this, let $x,y$ be two such prefixes, say $x$ is a prefix of $y$. Then $y = xz$, and so $xz$ is square-free while $yz = xz^2$ isn’t.

Alternatively, we can apply the pumping lemma to the language of all square-free words over $\{a,b,c\}$. If the pumping length is $n$, take the prefix of $w$ of length $n$, and pump it up so that it contains a square. Similarly, since the Thue–Morse sequence is an infinite binary cube-free sequence, the language of cube-free words over $\{a,b\}$ is not regular.

The latter argument shows that the language of square-free words over $\{a,b,c\}$ and the language of cube-free words over $\{a,b\}$ are not context-free. This leaves the following questions open:

  1. Is the language of non-square-free words over $\{a,b,c\}$ context-free?
  2. Is the language of non-cube-free words over $\{a,b\}$ context-free?
$\endgroup$
1
$\begingroup$

The language is regular for the reason you stated, and the regex you gave is also correct.

Since the language allows any prefix and any postfix, the only requirement is to have a duplicate substring inside the language.

For this reason, any word containing "aa" or "bb" is in the language. Any word with neither aa nor bb is either of the form "abab..." or "baba...". For words of length >= 4 the substring "ab" or "ba" occurs twice consecutively in the word, so the word is in the language.

$\endgroup$

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