Timeline for Fitting a regular grammar to strings from a PCFG: how big does it get?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2018 at 12:34 | comment | added | John L. | Basically, the first question is how to estimate/measure/evaluate how close is a CFG to a regular language. There are many ways. My example tries making it obvious that a simplistic measurement might not work perfectly. | |
| Dec 29, 2018 at 12:24 | comment | added | John L. | I noticed your attempt to emphasize non-regular-ness. However, you can just attach another piece to $G$, such as $\{a^nb^n\mid n\ge0\}$ to make it non-regular. | |
| Dec 29, 2018 at 10:39 | comment | added | Robin Ryder | I tried to phrase the question in a way that would specifically avoid this case, with $G$ a non-regular (P)CFG. | |
| Dec 29, 2018 at 9:17 | comment | added | John L. | That is exactly the point. I am saying there are ways to interpret the requirement of $\hat G$ that makes the solution uninteresting. | |
| Dec 28, 2018 at 8:11 | comment | added | Robin Ryder | Thank you for the links! However, I don't understand your example, since your $G$ is regular, so of course $\hat G=G$ works. | |
| Dec 26, 2018 at 10:55 | comment | added | John L. | Practical Experiments with Regular Approximation of Context-Free Languages seems interesting. | |
| Dec 26, 2018 at 10:16 | history | answered | John L. | CC BY-SA 4.0 |