Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Speaking in terms of automata and regular languages, how would it be possible for a string repeating some $w$ twice equal a string repeating that same $w$ thrice? That is, why is the language

$\qquad L = \{w \in \Sigma^ * \mid ww = www\}$

not empty? The only thing I can think of is $w = abab, ww = abababab, www = abababababab$, but I don't think this is correct.

share|cite|improve this question
Is this homework? Are you sure you read the question right? The language $L$ is not empty, but $L = \{\epsilon\}$. – Pål GD Feb 2 '13 at 13:51
up vote 6 down vote accepted

The only way that $w w = w w w$ is that $w = \epsilon$. Algebra of strings (for mathematician types, the free monoid on $\Sigma$) isn't that different from multiplication...

share|cite|improve this answer

A string of length $2$ cannot be equal to a string of length $3$. But a string constructed by concatenation of $2$ strings may be equal to a string constructed by concatenating $3$ strings. The empty string (denoted by $\epsilon$) is of length = $0$ and it's a member in $\Sigma^*$. If $w$ is chosen to be the empty string, then $\epsilon \epsilon = \epsilon \epsilon \epsilon$.

This is true because for any string $w$, $w\epsilon$ = $\epsilon w$ = $w$.

share|cite|improve this answer

It can be possible because of the empty string $ \epsilon$ which is a part of $\Sigma^*$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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