2.3 Regulární výrazy

Regulární výraz

Regulární výraz (RV) definujeme rekurzivně nad abecedou \(\Sigma\) takto:

\(\emptyset, \varepsilon, a\) jsou regulární výrazy pro všechna \(a \in \Sigma\).
Jsou-li \(x, y\) regulární výrazy nad \(\Sigma\), pak \((x + y)\), \((x \cdot y)\) a \((x)^*\) jsou regulární výrazy nad \(\Sigma\).
Priorita operátorů: Operátor iterace (\(^*\)) má nejvyšší prioritu, operátor zřetězení (\(\cdot\)) má druhou nejvyšší prioritu a operátor sjednocení (\(+\)) má nejnižší prioritu. Pokud chceme prioritu změnit, můžeme využít závorky.
Místo \(x \cdot y\) budeme často psát jen \(xy\).

Hodnota regulárního výrazu

Hodnota (jazyk) regulárního výrazu je regulární jazyk, který daný regulární výraz reprezentuje. Formálně definujeme hodnotu \(h(V)\) regulárního výrazu \(V\) následovně:

\(h(\emptyset) = \emptyset\) (prázdný regulární výraz reprezentuje prázdný jazyk),
\(h(\varepsilon) = \{\varepsilon\}\) (regulární výraz \(\varepsilon\) reprezentuje jednoprvkový jazyk s prvkem \(\varepsilon\)),
\(h(a) = \{a\}\), kde \(a \in \Sigma\),
\(h(x + y) = h(x) \cup h(y)\),
\(h(x \cdot y) = h(x) \cdot h(y)\),
\(h(x^*) = (h(x))^*\).

Definice (Identické, ekvivalentní a podobné regulární výrazy)

Identické, ekvivalentní a podobné r.v.

Regulární výrazy \(x, y\) nazveme identické (označíme \(x \equiv y\)), jestliže \(x\) a \(y\) jsou úplně stejné řetězce symbolů.

Regulární výrazy \(x, y\) nazveme ekvivalentní (označíme \(x = y\)), jestliže mají stejný jazyk, tj. \(L(x) = L(y)\). To znamená, že regulární množiny, které tyto výrazy popisují, jsou stejné.

Regulární výrazy \(x, y\) nazveme podobné (označíme \(x \cong y\)), jestliže se dají na sebe převést pomocí následujících identit:

\[ \begin{aligned} A_1 &: x + x = x \\ A_2 &: x + y = y + x \\ A_3 &: (x + y) + z = x + (y + z) \\ A_4 &: x + \emptyset = x \\ A_5 &: x \cdot \emptyset = \emptyset \cdot x = \emptyset \\ A_6 &: x \cdot \varepsilon = \varepsilon \cdot x = x \end{aligned} \]