Timeline for CFGs: detecting infinitely many derivations of a single string
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2015 at 6:00 | vote | accept | Bakkot | ||
| Apr 2, 2015 at 5:47 | history | edited | rici | CC BY-SA 3.0 |
added 470 characters in body
|
| Apr 2, 2015 at 5:34 | comment | added | rici | @Bakkot: I don't have a cite, but I think the proof is not difficult. It's clear that self-derivation is sufficient for an infinite number of derivations; the necessary part is absolutely clear if there are no nullable productions (without nullables, a derivation chain is monotonically non-shortening, and you can only have an infinite chain if there is some cycle). The same argument should work with nullables but the formalisation won't fit in a comment. I'll add the detection algorithm; it's not hard. | |
| Apr 2, 2015 at 5:22 | comment | added | Bakkot | That make sense (though I'd love a cite), but I'm still not sure how to check if a terminal derives itself indirectly, as in the example I give. | |
| Apr 2, 2015 at 4:58 | history | answered | rici | CC BY-SA 3.0 |