Revision as of 05:08, 13 November 2018 edit Cedar101 (talk \| contribs) Extended confirmed users 18,554 edits m →Example: ; : ← Previous edit		Revision as of 08:39, 1 June 2019 edit undo A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,578 edits mention exponential lower bound Tag: 2017 wikitext editor Next edit →
Line 294: Since ''q''<sub>0</sub> is the start state and ''q''<sub>1</sub> is the only accept state, the regular expression ''R''{{su\|p=2\|b=01}} denotes the set of all strings accepted by the automaton. == Computational complexity == The regular expression constructed by the algorithm may have size at least exponential in the input DFA. This exponential blowup is inevitable.<ref>{{Cite journal\|last=Gruber\|first=Hermann\|last2=Holzer\|first2=Markus\|date=2008\|editor-last=Aceto\|editor-first=Luca\|editor2-last=Damgård\|editor2-first=Ivan\|editor3-last=Goldberg\|editor3-first=Leslie Ann\|editor4-last=Halldórsson\|editor4-first=Magnús M.\|editor5-last=Ingólfsdóttir\|editor5-first=Anna\|editor6-last=Walukiewicz\|editor6-first=Igor\|title=Finite Automata, Digraph Connectivity, and Regular Expression Size\|url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_4\|journal=Automata, Languages and Programming\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=39–50\|doi=10.1007/978-3-540-70583-3_4\|isbn=9783540705833}}. Theorem 16.</ref> ==See also==

Kleene's algorithm: Difference between revisions