2.3.5 Derivace regulárních výrazů
Definice (Derivace regulárního výrazu)
Derivace regulárního výrazu
Derivace regulárního výrazu je jednoduše řečeno odebírání předpony (dle které derivujeme) u všech řetězců z jazyka, jenž je hodnotou derivovaného regulárního výrazu.
\[
\frac{dV}{dx} = V', \quad \text{kde } h(V') = \{y : xy \in h(V)\}
\]
Pravidla pro výpočet derivace
- \(\frac{dV}{d\varepsilon} = V\)
- Pro \(a, b \in \Sigma\) platí:
- \(\frac{d\varepsilon}{da} = \emptyset\)
- \(\frac{d\emptyset}{da} = \emptyset\)
- \(\frac{db}{da} = \begin{cases} \emptyset & \text{pokud } a \neq b \\ \varepsilon & \text{pokud } a = b \end{cases}\)
- \(\frac{d(U + V)}{da} = \frac{dU}{da} + \frac{dV}{da}\)
- \(\frac{d(UV)}{da} = \frac{dU}{da}V + \delta(U)\frac{dV}{da}\), kde \(\delta(U) = \begin{cases} \varepsilon & \text{pokud } \varepsilon \in h(U) \\ \emptyset & \text{jinak} \end{cases}\) (V původním textu zapsáno jako \(\{\frac{dV}{da} : \varepsilon \in h(U)\}\))
- \(\frac{d(V^*)}{da} = \frac{dV}{da} \cdot V^*\)
- Pro řetězec \(x = a_1a_2 \dots a_n\):
- \(\frac{dV}{dx} = \frac{d}{da_n} \left( \frac{d}{da_{n-1}} \left( \dots \frac{d}{da_2} \left( \frac{dV}{da_1} \right) \dots \right) \right)\)
Tip
Složitější regulární výraz je vhodné před vlastní derivací pokud možno zjednodušit.