Zadávání formalismů pro popis regulárních jazyků

Konečné automaty (DFA, NFA, NFA s ε-kroky)

Pro popis konečného automatu je třeba zapsat iniciální stav, přechodovou funkci a množinu koncových stavů. Validní automat musí obsahovat alespoň jeden (iniciální) stav.

Počáteční stav lze explicitně definovat jako init=stav na počátku zápisu automatu. Není-li počáteční stav takto specifikován, pak je jako počáteční stav vyhodnocen ten, který se jako první objeví v přechodové funkci.

Přechodová funkce sestává z přechodů zapsaných ve tvaru:

• (vstupní_stav,znak)=výstupní_stav pro deterministické automaty,
• (vstupní_stav,znak)={výstupní_stav1,výstupní_stav2, ..., výstupní_stavN} pro nedeterministické automaty.

V nedeterminstických automatech s ε-kroky lze místo znaku v přechodové funkci zapsat přechod pod prázdným slovem pomocí znaku ε nebo \e. Není vhodné uvádět pro stejnou dvojici (vstupní_stav,znak) v přechodové funkci více přechodů než jeden, vyhodnocovací služba v takovém případě bude brát v úvahu jenom poslední zaznamenaný přechod a upozorní na možný problém.

Zápis množiny koncových stavů je final={koncový_stav1,koncový_stav2, ..., koncový_stavN}, je na samém konci zápisu, oddělen aspoň jedním bílým znakem (mezera, tab, konec řádku) od přechodové funkce, a nelze jej vynechat.

Jako názvy stavů a znaků (identifikátory) lze použít:

• malá i velká písmena anglické abecedy, číslice 0–⁠9, znaky _ a ' nebo víceznakovou sekvenci uvedených symbolů,
• sekvenci jakýchkoli znaků kromě uvozovek a bílých znaků uzavřenou v uvozovkách (např. stav "{A,B,C}").

Bílé znaky mezi jednotlivými identifikátory nemají na vyhodnocení automatu vliv, nelze je však použít uvnitř názvů stavů nebo znaků.

Kanonický automat

Vyžaduje-li zadání úlohy kanonizaci automatu, použijte při pojmenovávání stavů postupně přirozená čísla od 1.

Příklady

DFA s explicitně definovaným počátečním stavem 0:

init=0
(0,a)=1 (0,b)=1
final={0,1}

DFA s implicitně definovaným počátečním stavem q_0:

(q_0, a) = q_1 (q_0, b) = q_1 (q_1, a) = q_1
final = {q_1}

NFA s počátečním stavem in:

init=in
(in,a)={fst,snd}
(fst,b)={snd}
(snd,b)={fst}
final={fst,snd}

NFA s epsilon kroky, počátečním stavem 0 a bez koncových stavů

(0,ε)={1} final={}

DFA s počátečním stavem A nad abecedou se znaky (a) a b:

(A,"(a)")=B (A,b)=C
(B,"(a)")=A (B,b)=B
(C,"(a)")=C (C,b)=A
final={A}

Regulární výrazy

Základní regulární výrazy jsou znak, prázdné slovo a prázdný jazyk:

• jako znaky lze použít malá i velká písmena anglické abecedy, číslice 0–⁠9 nebo také sekvence jakýchkoliv znaků v uvozovkách (kromě uvozovek a bílých znaků),
• prázdné slovo (epsilon) se značí jako \e nebo ε,
• prázdný jazyk je možné zapsat jako \0 (nula) nebo ∅.

Další regulární výrazy vznikají použitím operací iterace, zřetězení a sjednocení:

• regulární výraz je možné použít operátory ^* (iterace) a ^+ (pozitivní iterace), jako iterovaný se vyhodnotí nejbližší znak nebo regulární výraz v nejbližší závorce (nejblíže operátoru zleva),
• každé dva regulární výrazy lze zřetězit operátorem .,
• operaci +, která sémanticky odpovídá sjednocení dvou regulárních výrazů, lze zapsat pomocí operátoru +.

Operace jsou seřazeny podle priority od nejvyšší po nejnižší, nejdříve se tedy budou vyhodnocovat iterace, po nich zřetězení a s nejnižší prioritou operace +. Regulární výrazy je možné uzavírat do jednoduchých závorek ( ( a ) ), mezery jsou ignorovány. Znak je tvořen vždy jen jedním písmenem, více znaků následujících za sebou se vyhodnotí jako jejich implicitní zřetězení (ab je ekvivalentní a.b). Implicitně řetězit (bez explicitního zápisu pomocí tečky) lze nejen sekvenci znaků, ale také iterovaných regulárních výrazů a regulárních výrazů v závorkách (např. abc^*a(b+c) je ekvivalentní a.b.((c)^*).a.(b+c)).

Příklady:

• ab^* je ekvivalentní s a.((b)^*)
• a(bc)^*d je ekvivalentní s a.(b.c)^*.d
• (a + b + c^*) + \e je ekvivalentní s a + b + (c)^* + ε

Regulární gramatiky

Z gramatiky stačí definovat množinu pravidel, iniciálním neterminálem je první vyskytující se neterminál.

Neterminál je tvořen:

• jedním velkým písmenem anglické abecedy (např. S, A),
• sekvencí malých a velkých písmen anglické abecedy, číslic nebo znaku _ uzavřenou do lomených závorek <, > (např. <a>, <abAB>, <S_0>),
• jedním malým písmenem anglické abecedy nebo předchozím typem neterminálu (velké písmeno, sekvence v závorkách) s jedním nebo více apostrofy (např. S', a'', <aB_0>').

Terminálem může být jedno malé písmeno anglické abecedy, číslice 0–⁠9, jeden ze znaků ~, =, -, nebo sekvence jakýchkoliv znaků (kromě"` a bílých znaků) v uvozovkách.

Pravidla regulární gramatiky mohou být tvaru:

• Neterminál -> TerminálNeterminál (např. A -> aA),
• Neterminál -> Terminál (např. B -> b),
• Neterminál -> ε (např. S -> ε), ovšem pouze u iniciálního neterminálu, který se v tomto případě nesmí objevit v pravé straně žádného z pravidel.

Jako prázdné slovo (ε) lze psát ε nebo \e. Pravidla pro různé neterminály je třeba oddělit čárkou, středníkem nebo koncem řádku. Jako šipku lze psát -> i unicodový znak →. Více přepisovacích pravidel se stejnou levou stranou lze zapsat také pomocí oddělovače | (např. A -> aA | b). Mezery a taby lze mimo názvů terminálů a neterminálů používat libovolně (konec řádku však odděluje pravidla).

Příklady

S -> aS | aA | a; A -> bA | aS

A -> aB'
A -> bA
B' -> aB'
B' -> a

<init> → a<00X> | a<ab> | ε
<ab> → b

Bezkontextové gramatiky

Pro zápis CFG platí všechna pravidla jako pro regulární gramatiky kromě omezení tvaru pravé strany pravidel. Pravé strany pravidel tedy mohou obsahovat terminály i neterminály v libovolné kombinaci nebo ε (bezkontextová gramatika může obsahovat ε-kroky).

Příklad

S -> aAa | bBb | ε
A -> aAa | bab | bbb
B-> bBaBb | A | a

S → a<aB>B
<aB> → aB | ε
B → bB | ε