0

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.

xan
  • 2,053

1 Answers1

2

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.

xavierm02
  • 7,495
  • I don't understand. Can you elaborate? – xan May 04 '13 at 18:46
  • @xan Yup. Done :) – xavierm02 May 04 '13 at 18:47
  • @xavierm02 I don't understand. What happens if you apply your algorithm to $ab^* + a$? You get $f(a) = 0$, $f(b^) = 1$, $f(ab^) = 1$, but now $f(ab^* + a) = f(ab^) \wedge f(a) = 1 \wedge 0 = 0$. However, $ab^ + a = ab^*$... – J.-E. Pin Aug 20 '13 at 21:50
  • Yeah right. If $L(e_1)\subsetneq L(e_2)$ it can fail on the $e_1|e_2$... And maybe other related cases. – xavierm02 Aug 20 '13 at 22:14
  • I think transforming it to an automaton, computing the minimal DFA and turning it back into a regular expression (or doing something similar directly on the regular expression) would fix this. – xavierm02 Aug 20 '13 at 22:20