Nondeterministic finite automaton: Revision history

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 11:3011:30, 14 February 2025 Cedar101 talk contribs m 29,669 bytes +5 →Example: {{diagonal split header}} undo
curprev 11:2811:28, 14 February 2025 Cedar101 talk contribs 29,664 bytes −144 →Example: move state transition table into image caption undo

curprev 14:0214:02, 29 January 2025 Wp12897628 talk contribs 29,808 bytes +10 Undid revision 1271287067 by Jochen Burghardt (talk) Outer stars do nothing for trailing 1 on the left part (or 0 on the right part). Matching "001" requires one repetition (since each adds two 0), but fails to match the trailing 1. Converting the regexes to min-DFAs shows they are not equivalent. Putting /\A((1*01*0)*|(0*10*1)*)\z/ =~ '001' into any regex engine yields no match. undo Tag: Undo

curprev 19:0919:09, 28 January 2025 BaguetteDevourer talk contribs m 29,798 bytes +45 →Automaton: Unify formal definition with DFA undo

curprev 10:2510:25, 23 January 2025 Jochen Burghardt talk contribs 29,753 bytes −10 Undid revision 1271119136 by Wp12897628 (talk): not needed, due to the outer stars undo Tags: Undo Reverted

curprev 17:4117:41, 22 January 2025 Wp12897628 talk contribs 29,763 bytes +10 Fix regex in NFA-ε example (counterexamples for previous regex: "001" or "110") undo Tag: Reverted

curprev 01:4501:45, 29 November 2024 Tule-hog talk contribs 29,753 bytes +128 →References: try {sfn whitelist} fix undo
curprev 01:4101:41, 29 November 2024 Tule-hog talk contribs 29,625 bytes −142 merge rabin-scott refs undo
curprev 01:3801:38, 29 November 2024 Tule-hog talk contribs 29,767 bytes −421 →References: use template refs undo

curprev 20:1420:14, 30 August 2024 64.98.231.246 talk 30,880 bytes +9 →Informal introduction undo
curprev 06:3706:37, 30 August 2024 WikiLinuz talk contribs 30,871 bytes +136 Reverting edit(s) by Eldiem22 (talk) to rev. 1233092892 by David Eppstein: Unexplained content removal (RW 16.1) undo Tags: RW Undo
curprev 04:2504:25, 30 August 2024 Eldiem22 talk contribs m 30,735 bytes −136 →Closure properties undo Tag: Reverted

curprev 06:4606:46, 7 July 2024 David Eppstein talk contribs 30,871 bytes −24 →Equivalence to NFA: clarify undo

curprev 13:0013:00, 30 May 2024 Taroccoesbrocco talk contribs m 30,895 bytes −22 The subsection ===Recognized language=== just below assumes the definition of NFA without epsilon-moves. The definition of NFA with epsilon-moves is in the section ==NFA with ε-moves==. undo

curprev 12:1112:11, 11 March 2024 Jochen Burghardt talk contribs 30,917 bytes +3 →Automaton: indicate priority undo

curprev 08:3708:37, 10 March 2024 Boötes talk contribs 30,914 bytes +21 Fixed function definition to represent epsilon inputs, as epsilon is not implied to be an element of Sigma undo Tag: Visual edit

curprev 17:4917:49, 20 February 2024 Citation bot talk contribs 30,889 bytes −9 Altered url. URLs might have been anonymized. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 587/933 undo

curprev 19:0419:04, 22 December 2023 SimLibrarian talk contribs m 30,898 bytes −1 →Example: periods only for complete-sentence image captions (MOS:CAPFRAG) undo Tag: Visual edit

curprev 09:1909:19, 13 December 2023 Jochen Burghardt talk contribs 30,899 bytes +18 →Complexity: universality can easily be reduced to inclusion (viz., in a trivially universal automaton) undo
curprev 01:2901:29, 13 December 2023 A3nm talk contribs 30,881 bytes +62 →Complexity: link to counting problem undo Tag: 2017 wikitext editor
curprev 01:2601:26, 13 December 2023 A3nm talk contribs 30,819 bytes +57 →Complexity: link to emptiness problem article undo Tag: 2017 wikitext editor
curprev 00:4400:44, 13 December 2023 A3nm talk contribs m 30,762 bytes +8 +links undo Tag: 2017 wikitext editor

curprev 23:3823:38, 12 December 2023 MikaelMonet talk contribs 30,754 bytes +11 →Complexity undo
curprev 23:3623:36, 12 December 2023 MikaelMonet talk contribs 30,743 bytes +807 Added a section complexity, move the result that universality is PSPACE complete there (it had nothing to do in "implementation"), added the comlexity of other standart problems undo Tag: Visual edit: Switched

curprev 09:0109:01, 22 September 2023 Jochen Burghardt talk contribs 29,936 bytes −113 Undid revision 1176521915 by 60.243.180.50 (talk): implementations are usually based on DFAs, not NFAs, since the former are more efficient undo Tag: Undo
curprev 07:3507:35, 22 September 2023 60.243.180.50 talk 30,049 bytes +113 →Application of NFA undo Tag: Reverted

curprev 19:1119:11, 11 August 2023 Jochen Burghardt talk contribs 29,936 bytes +521 Undid revision 1169844952 by 2806:105E:F:4EB1:6816:4AFA:8FC7:3D3D (talk) undo Tags: Undo nowiki added
curprev 16:5616:56, 11 August 2023 2806:105e:f:4eb1:6816:4afa:8fc7:3d3d talk 29,415 bytes −521 Eliminar undo Tags: Reverted Visual edit Mobile edit Mobile web edit

curprev 09:0509:05, 8 August 2023 Jochen Burghardt talk contribs 29,936 bytes −26 Undid revision 1169284844 by 2601:646:9A00:C0F0:95F2:4953:D129:A1F5: "former" could be misunderstood as "immediately preceding" undo Tag: Undo
curprev 04:4904:49, 8 August 2023 2601:646:9a00:c0f0:95f2:4953:d129:a1f5 talk 29,962 bytes +26 No edit summary undo Tags: Reverted Mobile edit Mobile web edit

curprev 22:0122:01, 11 April 2023 Vstephen B talk contribs m 29,936 bytes +31 No edit summary undo

curprev 08:3908:39, 7 March 2023 Egeymi talk contribs 29,905 bytes +103 →Implementation: filled in 1 bare reference undo

curprev 12:5412:54, 26 January 2023 Rageking890 talk contribs 29,802 bytes +14 No edit summary undo Tags: Mobile edit Mobile web edit
curprev 12:5312:53, 26 January 2023 Rageking890 talk contribs 29,788 bytes +14 →Example: Improve mobile view undo Tags: Mobile edit Mobile web edit

curprev 14:2214:22, 14 November 2022 Hunan201p talk contribs 29,774 bytes +1 No edit summary undo

curprev 17:5217:52, 6 May 2022 TitleEditor talk contribs m 29,773 bytes +70 No edit summary undo Tags: Mobile edit Mobile app edit iOS app edit

curprev 20:0320:03, 30 April 2022 AnomieBOT talk contribs m 29,703 bytes +16 Dating maintenance tags: {{Clarify span}} undo
curprev 19:4319:43, 30 April 2022 Jochen Burghardt talk contribs 29,687 bytes +208 →Equivalence to NFA: finish paraphrasing H+U, without understanding yet their last case undo
curprev 19:3019:30, 30 April 2022 Jochen Burghardt talk contribs 29,479 bytes +1,621 →Equivalence to NFA: start paraphrasing H+U's proof undo
curprev 18:3318:33, 30 April 2022 Jochen Burghardt talk contribs 27,858 bytes +314 →Accepting states: replace unsourced section by close paraphrasing of H+U undo

14 February 2025

29 January 2025

28 January 2025

23 January 2025

22 January 2025

29 November 2024

28 November 2024

30 August 2024

7 July 2024

30 May 2024

11 March 2024

10 March 2024

29 February 2024

20 February 2024

22 December 2023

13 December 2023

12 December 2023

22 September 2023

11 August 2023

8 August 2023

11 April 2023

7 March 2023

26 January 2023

14 November 2022

6 May 2022

30 April 2022