1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this homework? Are you sure you read the question right? The language $L$ is not empty, but $L = \{\epsilon\}$. $\endgroup$ – Pål GD Feb 2 '13 at 13:51
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.