Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property: $$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq y\right) \wedge \left(x\text{ is a substring of } y\right) \right)$$
I spotted this problem while learning for test and unfortunately nothing clever comes to my mind. If $L$ is finite, I think the answer is always negative, because for any $x\in L$ that $\forall_{w\in L} |w|\le |x|$ we can't find such $y$. Don't know what happens if $L$ is infinite, I can't even imagine such $L$ that doesn't satisfy given condition. I would be very grateful for help.
Let $f$ be a function that takes your regular expression and returns $1$ if the language described verifies your property and $0$ otherwise.
$f\left(\varepsilon\right)=1$ because you can always find a word containing $\varepsilon$ (unless the language is empty of course...)
$f\left(l\right)=0$ because if you have a regular expression containing only a letter, you the language your property is false on that language
$f\left(e^*\right)=1$ because no matter what the regular expression $e$ is, you can always append one $e$ to any word of the language described by that expression while remaining in the language
$f\left(e_1|e_2\right)=f\left(e_1\right)\land f\left(e_2\right)$ because you need to be able to make the word bigger no matter if it's verifying $e_1$ or $e_2$
$f\left(e_1e_2\right)=f\left(e_1\right)\lor f\left(e_2\right)$ because to make a the word longer, you need to be able to make the part verifying $e_1$ bigger or the part verifying $e_2$ bigger
As J.-E. Pin pointed out, there is a problem in the $f\left(e_1|e_2\right)$: It assumes that a word satisfying $e_1$ can't be a factor of a word satisfying $e_2$ which is false. I think simplifying the regular expression by computing the automation it corresponds to, then the minimal DFA and then turning it back into a regular expression beforehand would make it work.