-1
$\begingroup$

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below.

My question is:

What is the logical reasoning to prove that any equation is the unique (only solution)? Particularly in this case, how can the procedure below logically lead to the proof that R=QP* must be the unique (only solution)?

Here is my understanding of the proof:

  1. Recursively substitute $R$ in $R=Q+RP$ with $Q+RP$
  2. Establish the recursive definition of $R$
  3. Generalize the definition to $R=QP^*$

Disclaimer: The proof below is second part of a 2-parts proof from the original Geeksforgeeks's proof of Arden’s Theorem. Originally, the proof starts out to prove $R=QP^*$ is a solution to $R=Q+RP$. I omitted this part here because I want to focus on the second part of the proof, which is to prove uniqueness. However, to clear any confusions, please allow the proof below to be based on the assumption that $R=QP^*$ is a solution to $R=Q+RP$ has been correctly proven prior and that $R=QP^*$ can be used as a corollary for proof below, which try to prove $R=QP^*$ is the unique solution to $R=Q+RP$, given P does not contain $\epsilon$

Given that $P$ and $Q$ are two regular expressions over $\Sigma$, and $P$ does not contain $\epsilon$. Start with: $$R = Q + RP$$

Now, replace $R$ by $R = Q + RP$: $$ \begin{align*} R &= Q + (Q + RP)P \\ &=Q + QP + RP^2 \end{align*} $$

Again, replace $R$ by $R = Q + RP$: $$ \begin{align*} R &= Q + QP + (Q+RP)P^2 \\ &= Q + QP + QP^2 + RP^3 \\ &= \cdots \\ &= Q + QP + QP^2 + \cdots + QP^n + RP^{n+1} \end{align*} $$

Now, replace $R$ by $R = QP^*$ to get $$ R = Q + QP + QP^2 + \cdots + QP^n + QP^*P^{n+1} $$

Taking $Q$ as a common factor, $$ \begin{align*} R &= Q(\epsilon + P + P^2 + \cdots + P^n + P^*P^{n+1}) \\ &= QP^*, \end{align*} $$ as $\epsilon + P + P^2 + \cdots + P^n + P^* P^{n+1}$ represents the closure of $P$.

Thus, $R = QP^*$ is the unique solution to $R = Q + RP$.

Clarifications:

I asked this question with the assumption that this is a valid proof $R=QP^*$ is the unique solution to $R=Q+RP$ (a). There are two basis for my assumption:

(1) This is the most popular proof found on the Web, I have included multiple sources as samples below. Across different authors, the proof takes exactly the same form as the procedure demonstrated above. Therefore, through inductive reasoning, I believe that this proof and its similar forms is a valid proof of (a). Otherwise, all those authors somehow collectively give a false proof.

(2) The procedure is logically and mathematically valid at each and every step, including the generalization of P* given that P does not contain $\epsilon$ as demonstrated above. Therefore, through deductive reasoning and (1), I believe that this proof and its similar forms is a valid proof of (a) until otherwise disproved through valid and sound counterargument.

Of course, what missing here is the intuitive reasoning from which one can derive that this proof indeed validly proves (a) to be true. Moreover, I am very curious and interested in the general intuitive and logical reasoning to prove anything as a unique solution.

I am not asking for a new proof. If for logical and/or mathematical reason, you can prove that this proof is invalid and MUST be discarded. Please present your evidence/counterargument in your answer. Please note that though I am not in any way qualify to be a
mathematician, I am quite aware of logical reasoning, as well as most fallacies and cognitive biases. So it might happen that I reject your proposed answer on the ground of invalid and/or unsound argument. This is in no way means that I want to offend you. If I made anyone feel so, I would like to apologize with my deepest sincerity. I am very appreciative of all the help I can get. Lastly, thank you Yuval Filmus, Hendrik Jan and D.W. who had been awesome people because you guys spent valuable time and efforts to put up with me for this question. Thanks guys.

Other sources from simple search of "Arden's Theorem Proof" on Google and Youtube

nesoacademy's Youtube Channel | Bhai Bhai Tutorials's Youtube Channel | Palak Chhajed's Youtube Channel | Theory of Automata and Formal Languages By Anand Sharma | tutorialspoint | sanfoundry

$\endgroup$
  • 3
    $\begingroup$ Any proof for uniqueness should use the necessary condition that $P$ does not contain $\varepsilon$. I do not recognize that here. $\endgroup$ – Hendrik Jan Dec 12 '19 at 8:53
  • $\begingroup$ what is confusing is why did we replace with QP* instead of only Q since R is equal to Q or RP. $\endgroup$ – awovu netux Dec 12 '19 at 16:50
  • 2
    $\begingroup$ Please don't post follow-up questions in the 'Your Answer' box. We are not a discussion forum, and we have strict quality standards for answers. Either edit the question (if you are the person who asked the question), or ask a new, self-contained question using the 'Ask Question' button in the upper-right. If you're requesting clarification, you'll be able to do that once you've participated in the site more, but for now we'd prefer that you focus on asking useful questions or answering other questions. $\endgroup$ – D.W. Dec 12 '19 at 17:26
  • $\begingroup$ @ Hendrik Jan the above proof is an excerpt from the original proof I linked on my OP. This excerpt was meant to be a reference and yes it is implied 𝑃 does not contain πœ€. Nevertheless, I will edit the post to clarify this implication. $\endgroup$ – langtutheky Dec 12 '19 at 20:00
  • 2
    $\begingroup$ This "proof" does not work. During the argumentation the fact that we want to prove is used half-way: Replace R by QP* and then at the end conclude R=QP*. Proofs don't work that way. Again, it is stated that P does not contain $\varepsilon$ but this is never actually used. $\endgroup$ – Hendrik Jan Dec 13 '19 at 11:25
2
$\begingroup$

Suppose $R = Q + RP$, where $\epsilon \notin P$.

Let us first prove by induction that $QP^i \subseteq R$ for all $i \geq 0$. The base case $Q \subseteq R$ is clear. Now suppose that we know that $QP^i \subseteq R$. Then $QP^{i+1} \subseteq RP \subseteq R$.

Since $QP^i \subseteq R$ for all $i \geq 0$, it follows that $QP^* \subseteq R$.

Conversely, let us prove by complete induction on $|w|$ that if $w \in R$ then $w \in QP^*$. Let $w \in R$, and assume (by induction) the claim for all shorter words. Since $R = Q + RP$, either $w \in Q$ or $w \in RP$. In the former case, clearly $w \in QP^*$. In the latter case, $w = xy$, where $x \in R$ and $y \in P$. Since $\epsilon \notin P$, $y \neq \epsilon$, and so $|x| < |w|$. Hence by the induction hypothesis, $x \in RP^*$. It follows that $w \in RP^*P \subseteq RP^*$.

We have shown that $R \subseteq QP^*$, and so $R = QP^*$.

For the case $\epsilon \in P$, see this answer.

The "proof" you provided isn't a proof. It is a very convoluted way to show that $QP^βˆ—$ is a solution, but it doesn't prove uniqueness at all. I suggest ignoring it.

$\endgroup$
  • $\begingroup$ Thanks for your answer, but I am not asking for another proof of the theorem. My main question is from the provided proof: what are the underline assumptions and logical reasonings that built up that proof for uniqueness? If possible, please provide an intuitive answer with easy-to-understand language. I am sorry but reading induction proof is not naturally intuitive, at least to me. Thanks. $\endgroup$ – langtutheky Dec 13 '19 at 0:15
  • 2
    $\begingroup$ As pointed out in the comments to your post, the proof in your post is very sloppy (which is to say, false). I suggest ignoring it. As to a more intuitive proof, unfortunately you cannot do mathematics without doing mathematics. $\endgroup$ – Yuval Filmus Dec 13 '19 at 0:18
  • 2
    $\begingroup$ The "proof" you provided isn't a proof. It is a very convoluted way to show that $QP^*$ is a solution, which amounts to the simple statement $QP^* = Q + QP^*P$, which follows from $P^* = \epsilon + P^*P$. It doesn't prove uniqueness at all. $\endgroup$ – Yuval Filmus Dec 13 '19 at 20:20
  • 2
    $\begingroup$ As for geeksforgeeks, that may be useful for a variety of purposes and I appreciate that you trust it and have found it useful, but I don't consider it a reputable primary source for material about theoretical computer science. It might be better for other things. Regardless of the source, the "proof" shown there is not a good proof of the claim. $\endgroup$ – D.W. Dec 13 '19 at 20:54
  • 1
    $\begingroup$ @langtutheky, thanks. Got it. I edited his answer to add the relevant parts of his comments to the answer. With that edit, hopefully this should answer your question. Your question was: "How does this prove that the solution is unique?" and Yuval's answer is "It doesn't, but here is how you could prove that". I hope this makes sense. $\endgroup$ – D.W. Dec 13 '19 at 22:16
2
$\begingroup$

This is not a valid proof.

You ask for the intuitive reasoning that makes this proof valid, but there's no amount of intuitive reasoning you can add to make it valid. It's just simply not a good proof. It's not a matter of adding intuition; there is no rescuing it.

A valid proof starts with facts that are known to be true; then each derives a new fact from previously known facts, using a valid inference rule or axiom. The so-called proof you have listed does not take that form. For instance, let me highlight two flaws:

  • The first step of the "proof" you refer to says "Now, replacing R by R = QP*, we get". This first step is already not valid. It makes an assumption that is not justified (it assumes that we know that R = QP*); so this step is not valid. Basically, the proof is flawed because it uses a circular argument: it starts by assuming what is to be proved, and derives what is to be proved. That proves nothing. Since you said you know logical fallacies, this is the fallacy of circular reasoning.

  • The second part of the "proof" again has the same flaw, where it says "Now, replace R by R = QP*". Here it is assuming what is to be proven.

  • The "proof" doesn't have the right structure to prove uniqueness. You can't prove that $x=5$ is the unique solution to an equation by first assuming that $x=5$ and then proving that it follows that $x=5$. It doesn't do anything to show that the solution is unique. It just claims "Thus, R = QP* is the unique solution", but without any justification for that statement. It doesn't even try to explain the justification -- we are forced to guess.


I think the primary lesson here is that I suggest you adjust how you judge the credibility of sources of technical information.

I realize you found this proof on a popular website, but popularity is not a guarantee of correctness; it is merely a hint that is sometimes useful. I realize that you found it on multiple websites, but that is not strong evidence; it's not unusual on the Internet to find multiple people copy-pasting the same wrong thing. I realize that GeeksforGeeks is highly regarded by some and might be useful for some purposes (e.g., particularly for coding-contest-style questions and interview-style questions), but in my experience, its quality is highly variable, and in particular, it is not a reliable resource for mathematical and theoretical topics. I have personally seen multiple articles there that are sloppy, a poor reference, or just plain wrong. Now I've seen one more. It might also be useful to mention that articles on Geeksforgeeks are not written by a single person -- they are written by many different authors, some of whom might be more knowledgeable than others, and in any case, the authors are only people, so they can make mistakes.

If you want to find credible resources, a better place is to find a well-regarded textbook on automata theory or the theory of formal languages. That will be a much more reliable reference than Geeksforgeeks.

I'd also encourage you to reflect on why you've been having a hard time believing it when three separate people have told you that the article was wrong -- two of whom are, as it happens, experts on this subject. That might be an enlightening exercise.

$\endgroup$
  • $\begingroup$ Regarding your first 2 points, it's not fallacy of circular reasoning. In the original GeeksforGeeks proof, which I hoped that you investigated thoroughly, this was actually a 2-parts proof. The first part proved that $R=QP^*$ is a solution to $R=Q+RP$. The second part then proved that $R=QP^*$ is a unique solution to $R=Q+RP$ given P does not contain $\epsilon$. From the first part, we then use $R=QP^*$ as (corollary)[en.wikipedia.org/wiki/Corollary] for the second part of the proof to prove uniqueness. The proof I shown above is one of the two part proof; its my fault. $\endgroup$ – langtutheky Dec 14 '19 at 4:56
  • $\begingroup$ Regarding your last point, I think its targeted the same concern that @Hendrik Jan which I have discussed thoroughly in the comment section of OP with him. So the proof leads to the recursive definition of R. From there, the proof did not magically "replace R by QP* and then at the end conclude R=QP*". P* appears because of the generalization of (πœ€ + P + 𝑃2 + 𝑃3+...) to be equivalent to P* given that P does not contain πœ€. This is a closure of P. So from recursive definition of R to the the generalization of P* from (πœ€ + P + 𝑃2 + 𝑃3+...), the proof conclude uniqueness. $\endgroup$ – langtutheky Dec 14 '19 at 5:03
  • $\begingroup$ Regarding textbook sources, Theory of Automata and Formal Languages. $\endgroup$ – langtutheky Dec 14 '19 at 5:07
  • $\begingroup$ Another textbook source that use similar proof technique of uniqueness, Introduction to Automata Theory, Formal Languages and Computation $\endgroup$ – langtutheky Dec 14 '19 at 5:08
  • $\begingroup$ @langtutheky, Regarding the proof of correctness, I did read the Geeksforgeeks "proof" carefully, and the second part of their "proof" proved no such thing. My critique is exactly of the second part of their "proof"; that's where the worst problems in their "proof" are. It totally is circular reasoning. I stand by my answer. $\endgroup$ – D.W. Dec 14 '19 at 5:41

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.