Content deleted Content added
→Computational complexity: explain what "inevitable" means |
move complexity discussion to a better place |
||
Line 20:
By induction on ''k'', it can be shown that the length<ref>More precisely, the number of regular-expression symbols, "''a''<sub>''i''</sub>", "ε", "|", "<sup>*</sup>", "·"; not counting parantheses.</ref> of each expression ''R''{{su|p=''k''|b=''ij''}} is at most {{sfrac|4<sup>''k''+1</sup>(6''s''+7) - 4|3}} symbols, where ''s'' denotes the number of characters in Σ.
Therefore, the length of the regular expression representing the language accepted by ''M'' is at most {{sfrac|4<sup>''n''+1</sup>(6''s''+7)''f'' - ''f'' - 3|3}} symbols, where ''f'' denotes the number of final states.
In practice, the size of the regular expression obtained by running the algorithm can be very different depending on the order in which the states are considered by the procedure, i.e., the order in which they are numbered from 0 to ''n''.
==Example==
Line 294 ⟶ 297:
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.
▲The regular expression constructed by the algorithm may have size at least exponential in the input DFA. This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size.<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==
| |||