Úvod

Regulární jazyky studujeme proto, že konečný automat přijme slovo právě tehdy, když je slo­vem v jemu odpovídajícím regulárním jazyce. To umožňuje zkontrolovat, zda je na­příklad počítačový program napsán podle pro něj definovaných pravidel. Nebo také získat odpověď na otázku, co může konečný automat dělat se slovy, jejichž délka překračuje kapacitu jeho paměti.

Regulární výrazy

Regulární jazyk můžeme definovat pomocí operací definovaných v teorii formálních jazyků. Pro přesný a přehledný zápis i jazyků obsahujících nekonečný či ničím neomezený počet slov slouží právě regulární výrazy. Vycházíme při tom z následující věty:

Regulární jazyk je právě takový jazyk, ktrý je možné popsat regulárním výrazem.

Induktivní definice regulárních výrazů nad abecedou Σ:

Pokud

∅ označuje prázdný jazyk (jazyk neobsahující žádné slovo),
ε označuje jazyk {ε} (jazyk obsahující jako slovo pouze prázdný znak),
a označuje jazyk {a} (jazyk obsahující jeden znak z abecedy znaků),

pak ∅, ε, a a (kde a ∈ Σ) jsou regulární výrazy.

Pokud

(α + β) označuje sjednocení jazyků označených  α a β,
(α · β) označuje zřetězení jazyků označených α a β,
(α*) označuje iteraci jazyka označeného α,

pak platí, že pokud α, β jsou regulární výrazy, pak i (α + β), (α · β), (α*) jsou regulární výrazy.

Neexistují žádné další regulární výrazy než ty definované podle předchozích pravidel.

Operace zřetězení nám vlastně zaručuje, že libovolná posloupnost znaků konečné délky je v dané abecedě regulární výraz, který definuje slovo regulárního jazyka, o němž víme, že je rozpoznatelné konečným automatem.

Podle definice zavede iterace L* do množiny slov regulárního jazyka prázdné slovo ε jako „zřetězení nula slov z L“. Zřetězením nula slov vznikne prázdné slovo ε také v prázdném jazyce

Příklad (též na závorky):

Podle definice jsou 0 i 1 regulární výrazy.

Protože 0 i 1 jsou regulární výrazy, je i (0 + 1) regulární výraz.

Protože 0 je regulární výraz, je i (0*) regulární výraz.

Protože (0 + 1) i (0*) jsou regulární výrazy, je i ((0  + 1) · (0*)) regulární výraz.

Je zřejmé, že při vytváření regulárního výrazu pomocí induktivní definice, se nahromadilo velké množství závorek. Aby byl zápis regulárních výrazů přehlednější a stručnější, používáme následují pravidla:
Vynecháváme vnější pár závorek.
Vynecháváme závorky, které jsou zbytečné vzhledem k asociativitě operací sjednocení (+) a zřetězení (·).
Vynecháváme závorky, které jsou zbytečné vzhledem k prioritě operací (nejvyšší prioritu má iterace (*), menší zřetězení (·) a nejmenší sjednocení (+)).
Nepíšeme tečku pro zřetězení.

Místo

((0 + 1) · (0*)),

pak píšeme

(0  + 1)0*.

Regulární jazyky

Regulární jazyk definovaný regulárním výrazem α označujeme zápisem [α]. Tohoto zápisu budeme nyní bohatě využívat.

Ukázky využití regulárních výrazů při popisu regulárních jazyků:

[800000] = {800000} -jedno slovo.
Každé slovo konečné délky je na základě operace zřetězení znaků slovem regulárního jazyka.

[barbara + celarent + darii + ferio] = {barbara, celarent, darii, ferio} -jazyk tvořený více slovy.
Pomocí operace sjednocení můžeme vytvářet seznamy slov zadávaného regulárního jazyka.

[(0 + 1)*] = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000,…}
-jazyk obsahující všecha slova nad abecedou Σ = {0, 1}.
Výraz [(0 + 1)*] se nám bude hodit jako součást regulárních výrazů při tvorbě jazyků s neomezeně dlouhými slovy. (V souvislosti s obecnou definicí jazyka nad abecedou Σ jej lze definovat také jako L = Σ*.)

[1(0 + 1)*1] = {11, 101, 111, 1001, 1011, 1101, 1111, 10001, 10011, 10101, 10111, 11001…} -jazyk všech možných slov v abecedě Σ = {0, 1} začínajících a končících 1.
Iterace (0 + 1)* vytváří nekonečné množství slov, která začínají a končí na 1. Ale teprve, když před ní i za ní pomocí operace zřetězení dáme 1, máme záruku, že všechna budou splňovat naší podmínku a že žádné nebude chybět. Uplatní se i prázdné slovo ε, které vznikne při operaci iterace.

[0 + 1(0 + 1)*] = {0, 1, 10, 11, 100, 101, 110, 111, 1000,…} -jazyk je tvořen čísly ve dvojkové soustavě zapsanými bez nul před prvními jedničkami.

[(abc)⁺] = {abc, abcabc, abcabcabc,…} -jazyk všech slov v nichž se libovolně krát opakuje posloupnost abc.
Protože jsme použili Σ⁺, získali jsme jazyk bez prázdného slova.

[01⁺0] = {010, 0110, 01110,…} -jazyk, u kterého počet jedniček mezi nulami udává odpovídající přirozené číslo.
(Je třeba si dát pozor na to, že iterace má ve výrazu přednost před zřetězením. To znamená, že bez vynechání vnitřních závorek je výraz 0(1⁺)0.

(0 + 1)*111(0 + 1)* -regulární výraz pro jazyk tvořený všemi slovy obsahujícími alespoň jednou tři jedničky bezprostředně za sebou.

(0*10*10*)* -regulární výraz pro jazyk tvořený všemi slovy obsahujícími sudý počet symbolů 1.
Pro správné pochopení tohoto výrazu je třeba dát pozor na prioritu oprátoru iterace.

0*10* + 1(0*10*10*)* -regulární výraz pro jazyk tvořený všemi slovy obsahujícími lichý počet symbolů 1.
I zde platí, že pro správné pochopení tohoto výrazu je třeba dát opět pozor na prioritu oprátoru iterace.

Pro nás je podstatné, že každý jazyk, který je možné vyjádřit regulárním výrazem, je regulární, a že jazyk je regulární právě tehdy, když je rozpoznávaný nějakým konečným automatem.