Regulární výraz

Regulární výrazy zavedl americký matematik Stephen Cole Kleene.

VĚTA: Libovolný jazyk je regulární, právě když je přijímaný konečným automatem.

Regulární výraz V nad abecedou Σ je definován jako:
  1. ∅, ε, a jsou regulární výrazy pro všechna a ∈ Σ
  2. Jsou-li x, y regulární výrazy nad Σ, pak:
    • (x + y) (sjednocení, alternativa),
    • (x.y) (zřetězení) a
    • (x)* (iterace)
    jsou regulární výrazy nad Σ.
Hodnota h(x) regulární výrazu x je definována jako:
  • h(∅) = ∅, h(ε) = ε, h(a) = a,
  • h(x+y) = h(x)∪h(y),
    h(x.y) = h(x).h(y),
    h(x*) = (h(x))*.
Regulární výrazy jsou identické (značíme x ≡ y), jestliže x a y jsou uplně stejné řetězce symbolů.

Úprava regulárních jazyků

  1. ∅* = ε
    nultá iterace jakéhokoliv jazyka je ε

  2. x* + x = x*
    iterace je obsažena v x*

  3. (x*)* = x*
    točíme se závorce nebo uvnitř

  4. (x + y)* = (x*y*)*
    výsledek je libovolný počet x nebo y.

  5. x*y = y + x*xy

  6. x*y = y + xx*y

  7. x*y = x*(y + xy + x2y + ... + xn-1y)

  8. xx* = x*, pokud ε ∈ h(x)

  9. (xy)*x = x(yx)*

  10. (x + y)*x = x(yx)*

Související