04.3 Ekvivalence RV
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
Ekvivalence regulárních výrazů
# Identické
Označíme $x \equiv y$
Jestliže jsou $x$ a $y$ úplně stejné řetězce symbolů
Když jsou RV identické, jsou i ekvivalentní i podobné
# Podobné
- Označíme $x \cong y$
- Jestliže se dají na sebe převést pomocí následujících identit $$ \begin{flalign} &A_1: \quad x+x=x &&\\ &A_2: \quad x+y=y+x &&\\ &A_3: \quad(x+y)+z=x+(y+z) &&\\ &A_4: \quad x+\emptyset=x &&\\ &A_5: \quad x . \emptyset=\emptyset . x=\emptyset &&\\ &A_6: \quad x . \varepsilon=\varepsilon . x=x &&\\ \end{flalign} $$
- Když jsou RV podobné, jsou i ekvivalentní
Poznámka $x^{}= \varepsilon + xx^{}$ Tedy $xx^{*}$ je jakoby $x^+$
# Ekvivalentní
- Označíme $x = y$
- Jestliže mají $x$ a $y$ stejnou hodnotu $h(x) = h(y)$