Timeline for Uniqueness of solution in Arden's theorem
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 14, 2019 at 6:08 | history | edited | langtutheky | CC BY-SA 4.0 |
Add: Disclaimers
|
| Dec 14, 2019 at 3:32 | answer | added | D.W.♦ | timeline score: 2 | |
| Dec 14, 2019 at 1:24 | history | edited | langtutheky | CC BY-SA 4.0 |
Fixed: typos
|
| Dec 13, 2019 at 23:10 | review | Close votes | |||
| Dec 19, 2019 at 3:05 | |||||
| Dec 13, 2019 at 23:07 | comment | added | langtutheky | @Hendrik Jan That statement is wrong. First, in Kleene closure $P^* = P^0 + P^1 + P^2+...$ where $P^0$={𝜀}. It is necessary that 𝜀 is not part of P, otherwise 𝜀+𝜀+𝜀+𝜀+... would be valid for any $P^*$ which is wrong. Second, this contradict with the definition of $P^+$ as well "L+ must either be composed from one element of L and finitely many non-empty terms in L or is just an element of L. Conversely, L* = {ε} ∪ L+"source. Therefore, for Kleene closure $P^*$, P must not contain 𝜀. | |
| Dec 13, 2019 at 22:44 | comment | added | Hendrik Jan | Note that Kleene closure $P^* = P^0+P^1+P^2+\dots$ by definition, where $P^0=\{\varepsilon\}$. This is independent on whether $\varepsilon\in P$ or not. | |
| Dec 13, 2019 at 22:41 | history | edited | langtutheky | CC BY-SA 4.0 |
The last edit changed the original question's wording and thus, its intention. This is the original statements from the first version.
|
| Dec 13, 2019 at 20:17 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 701 characters in body
|
| Dec 13, 2019 at 19:06 | comment | added | langtutheky | @Hendrik Jan In addition, it just came to me that you did not realize 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. | |
| Dec 13, 2019 at 18:54 | comment | added | langtutheky | @Hendrik Jan I am not sure what you mean that this proof does not work. First, the fact that P does not contain 𝜀 is used in the last line of the proof to generalize (𝜀 + P + $P^2$ + $P^3$+...) to be equivalent with P*. If P does contain 𝜀 then this generalization is false. Second, please do a simple google "Arden's Theorem Proof" and pick any of the top results, all those professionals use the same proof technique of R substitution as presented here. Their procedures follows exactly the one I described above so I am not sure how this proof "does not work" for you. | |
| Dec 13, 2019 at 11:25 | comment | added | Hendrik Jan | 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. | |
| Dec 12, 2019 at 23:51 | answer | added | Yuval Filmus | timeline score: 4 | |
| Dec 12, 2019 at 20:24 | history | edited | langtutheky | CC BY-SA 4.0 |
edited tags
|
| Dec 12, 2019 at 20:20 | comment | added | langtutheky | @awovu netux I think you confused yourself, R is logically equivalent to the entire expression Q+RP (Q or RP), but R is not logically equivalent to either Q or RP individually as you implied. So you cannot substitute Q into R. QP*, however, is logically equivalent to R as the proof demonstrated. Therefore, QP* can be use as substitution for R. | |
| Dec 12, 2019 at 20:08 | history | edited | langtutheky | CC BY-SA 4.0 |
added 101 characters in body
|
| Dec 12, 2019 at 20:00 | comment | added | langtutheky | @ 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. | |
| Dec 12, 2019 at 17:26 | comment | added | D.W.♦ | 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. | |
| Dec 12, 2019 at 16:50 | comment | added | awovu netux | what is confusing is why did we replace with QP* instead of only Q since R is equal to Q or RP. | |
| Dec 12, 2019 at 8:53 | comment | added | Hendrik Jan | Any proof for uniqueness should use the necessary condition that $P$ does not contain $\varepsilon$. I do not recognize that here. | |
| Dec 12, 2019 at 4:00 | review | First posts | |||
| Dec 12, 2019 at 19:04 | |||||
| Dec 12, 2019 at 3:55 | history | asked | langtutheky | CC BY-SA 4.0 |