✖

Regulární výrazy

Kapitoly: Regulární výrazy, Převod reguláru na automat, Zobecněný NKA, Převod automat na regulár

Regulární výraz je textový řetězec, který umožňuje popsat nějakou množinu slov. Regulární výrazy také můžeme chápat jako jednoduchý způsob jak popsat konečný automat.

Co je to regulární výraz

V aritmetice používáme symboly jako · a + k sestavení výrazu jako například (2 + 3) · 4. Vyhodnocením tohoto výrazu získáme číslo. Regulární výraz je nějaká posloupnost znaků a několika speciálních symbolů, např. a(x∪ y), jejichž vyhodnocením je (formální) jazyk. Výsledkem výrazu (2 + 3) · 4 je číslo 20, výsledkem regulárního výrazu a(x∪ y) je množina dvou slov „ax“, „ay“.

Jak bychom vyhodnotili předchozí regulární výraz a(x∪ y)? Každé písmeno je ve skutečnosti zkratka za jednobodovou množinu obsahující dané písmeno a skryté násobení je zřetězení slov. Regulární výraz bychom mohli přepsat „v plném znění“ takto:

$$ \left\{a\right\}\circ\left(\left\{x\right\}\cup\left\{y\right\}\right) $$

Dále bychom to vyhodnotili takto: sjednocení {x}∪{y} nám vytvoří jazyk {x,y}. Zřetězením jazyků {a} a {x,y} získáme jazyk {ax, ay}.

Regulární výrazy se velmi často používají v programování a většina programovacích jazyků má regulární výrazy nějakým způsobem implementované. Regulární výrazy se tak používají například pro ověřování, zda uživatelem zadaný text splňuje určitá kritéria (např. jestli je to platný email, platné datum apod.), dále pro nahrazování textů (např. můžeme chtít nahradit všechny výskyty URL v textu na klikatelné odkazy apod.).

Reálné implemetnace regulárních jazyků jsou většinou silnější než zde popsané regulární výrazy a používají mírně odlišnou, ale hlavně složitější syntaxi.

Definice regulárního výrazu

Regulární výraz budeme definovat nad nějakou abecedou $\Sigma$. Pak řekneme, že regulární výraz je:

  1. a, kde $a \in \Sigma$. Tj. samotný znak abecedy je regulární výraz.
  2. ε: prázdné slovo, v programování se také zapisuje jako prázdné uvozovky \“\“.
  3. ∅: regulární výraz musí umět popsat i prázdný jazyk, takže prázdný jazyk je regulární výraz.
  4. (R1 ∪ R2), kde R1, R2 jsou regulární výrazy.
  5. $(R_1 \circ R_2)$, kde R1, R2 jsou regulární výrazy.
  6. $(R^\ast)$, kde R je regulární výraz.

Místo symbolu ∪ z bodu 4 můžeme také používat symbol svislítka: |. Místo symbolu $\circ$ nemusíme používat nic. Podobně jako většinou přímo nepíšeme symbol násobení, středovou tečku · , tak většinou ani nepíšeme symbol zřetězení $\circ$. Tyto regulární výrazy tak jsou totožné: $a\circ (b\cup c)$ a a(b|c).

Co jednotlivé operátory znamenají?

  • ∪ nebo | značí sjednocení jazyků.
  • $\circ$ značí zřetězení jazyků.
  • $^\ast$ značí uzávěr jazyka.

Příklady:

  • a značí jednoduchý jazyk {a}.
  • a|b značí jazyk skládající se ze dvou slov {a, b}.
  • $a\circ b$ značí jazyk {ab}.
  • a(b|c)d značí jazyk {abd, acd}.
  • $a(b^\ast)$ značí jazyk všech slov, které začínají písmenem „a“, za kterým následuje libovolný počet písmen „b“.
  • $(ab)^\ast$ značí jazyk všech slov {ε, ab, abab, ababab, …}.
  • $0^\ast10^\ast$ značí jazyk všech binárních slova, které obsahují právě jednu jedničku. (Všimněte si, že přesnější by bylo naspat tento výraz takto: $(0^\ast)1(0^\ast)$, ale když je zápis čitelný i bez toho, můžeme závorky vynechat.)
  • $\Sigma^\ast1\Sigma^\ast$ značí jazyk obsahující alespoň jednu jedničku.
  • $(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^\ast$ značí jazyk všech přirozených čísel.

Dále si ukážeme ekvivalenci mezi regulárními výrazy a konečnými automaty. Tady pro každý regulární výraz, jehož vyhodnocením je jazyk R, existuje konečný automat A, pro který platí L(A) = R a naopak.

Zdroje