Timeline for How can every regex be accepted by an infinite number of finite automata?
Current License: CC BY-SA 3.0
Post Revisions
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2017 at 18:40 | comment | added | Thumbnail | There are also, for any regular expression, an infinite number of equivalents. The significant thing is that there is a unique minimal DFA for any regular expression. You minimise by two transformations: 1. removing all inaccessible states and 2. equating all indistinguishable ones. You can work (1) and (2) in either order. Running them in reverse generates the infinity of equivalents. Read the first couple of chapters of John Conway's Regular Algebra and Finite Machines for real insight. | |
| Apr 17, 2017 at 17:10 | answer | added | Devendra Bhave | timeline score: 0 | |
| Apr 17, 2017 at 11:22 | comment | added | Raphael | Note that the reverse statement is also true. This is often the case for useful models of computation: every object they describe has infinitely many description. Think of adding useless stuff; don't fall into the trap if thinking only about minimal automata. | |
| Apr 17, 2017 at 11:21 | history | edited | Raphael |
edited tags
|
|
| Apr 17, 2017 at 10:37 | answer | added | David Richerby | timeline score: 7 | |
| Apr 17, 2017 at 9:53 | vote | accept | Chris B | ||
| Apr 17, 2017 at 8:56 | answer | added | gsz | timeline score: -1 | |
| Apr 17, 2017 at 8:54 | answer | added | abc | timeline score: 3 | |
| Apr 17, 2017 at 8:43 | review | First posts | |||
| Apr 17, 2017 at 13:52 | |||||
| Apr 17, 2017 at 8:39 | history | asked | Chris B | CC BY-SA 3.0 |