04.1 Regulární výrazy

Last updated Nov 9, 2022

• Regulární výraz $V$ nad abecedou $\Sigma$ je definován:
  • $\emptyset, \varepsilon, a$ - RV pro všechna $a \in \Sigma$
  • Jsou li $x,y$ RV nad $\Sigma$, pak i následující jsou RV nad $\Sigma$:
    • $(x+y)$ - sjednocení, alternative
    • $(x.y)$ - zřetězení
    • $(x)^*$ - iterace

Poznámka Tečky a závorky lze vynechat, pokud je to jednoznačené

• $x^{}= \varepsilon + xx^{}$

• Tedy $xx^{*}$ je jakoby $x^+$

• Řešení regulárních rovnic - Nechť $x, \alpha, \beta$ jsou RV, pak platí:

  • $V_{1}: x = x\alpha + \beta \Rightarrow x = \beta \alpha^*$ (levá regulární rovnice)
  • $V_{2}: x = \alpha x + \beta \Rightarrow x = \alpha^{*}\beta$ (pravá regulární rovnice)
  • pozn. $\alpha$ je rekurentní člen, $\beta$ je ukončovací člen

Věty v teorii regulárních výrazů