Content deleted Content added
→Algorithm description: guessed sect. and page number in Kleene's 1956 paper (not *quite* sure, crosscheck appreciated) |
→Algorithm description: upper bound for the length of R^k_{ij} |
||
Line 17:
After that, in each step the expressions ''R''{{su|p=''k''|b=''ij''}} are computed from the previous ones by
:''R''{{su|p=''k''|b=''ij''}} = ''R''{{su|p=''k''-1|b=''ik''}} (''R''{{su|p=''k''-1|b=''kk''}})<sup>*</sup> ''R''{{su|p=''k''-1|b=''kj''}} | ''R''{{su|p=''k''-1|b=''ij''}}
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}}, where ''s'' denotes the number of characters in Σ.
==Example==
| |||