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ů.

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 pravidel 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. Pokud se pro stejnou dvojici (vstupní_stav,znak) objeví v přechodové funkci více přechodů, vyhodnocovací služba 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 a nelze jej vynechat.

Validní automat musí obsahovat alespoň jeden stav.

V názvech stavů a znaků lze použít malá i velká písmena anglické abecedy, číslice a znaky _ (!). Lze tvořit i víceznakové sekvence jako názvy stavů. Bílé znaky (mezera, tab, konec řádku) nemají na vyhodnocení automatu vliv.

Příklady:

• init=0 (0,a)=1 (0,b)=1 final={0,1}
• (q_0, a) = q_1 (q_0, b) = q_1 (q_1, a) = q_1 final = {q_1} (počáteční stav bude q_0)
• init=init (init,a)={fst,snd} (fst,b)={snd} (snd,b)={fst} final={fst,snd}
• (0,ε)={1} final={}

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 a čísla;
• prázdné slovo (epsilon) se značí jako \e nebo ε;
• prázdný jazyk je možné zapsat jako \0 nebo ∅.

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

• regulární výraz je možné iterovat 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 .;
• 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 sjednocení. Regulární výrazy je možné uzavírat do jednoduchých závorek ( ( a ) ), mezery jsou ignorovány. Implicitní zřetězení (bez explicitního zápisu pomocí tečky) funguje pro sekvence znaků, iterovaných regulárních výrazů a regulárních výrazů v závorkách. 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).

Příklady:

• ab^* se vyhodnotí jako a.((b)^*)
• a(bc)^*d se vyhodnotí jako a.(b.c)^*.d
• (a + b + c^*) + \e se vyhodnotí jako a + b + (c)^* + ε

Regulární gramatiky

Z gramatiky stačí definovat množinu pravidel ve tvaru S -> aS | a, kde S je neterminál a a je terminál. Více možných přepisů pro stejný neterminál lze zapsat jako více pravidel nebo také pomocí oddělovače |. Jednotlivá pravidla pro každý neterminál je třeba oddělit středníkem nebo koncem řádku. Jako šipku lze psát -> i unicodový znak →.

Neterminál je tvořen (hovoříme o písmenech anglické abecedy):

• jedním velkým písmenem (např. S, A),
• jedním malým nebo velkým písmenem s jedním nebo více apostrofy (např. S', a''),
• sekvencí malých a velkých písmen, čísel nebo znaku _ uzavřenou do lomených závorek <> (např. <abAB>, <S_0>).

Terminálem může být jedno malé písmeno anglické abecedy nebo číslo 0-9.

Regulární gramatika může také generovat prázdné slovo, pak lze v pravidle použít symbol ε nebo \e (ovšem pouze u iniciálního neterminálu, který se v tomto případě nesmí objevit v pravé straně žádného z pravidel).

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 pravidel. Pravé strany pravidel nemusí být jen typu samotný terminál nebo dvojice terminál a neterminál, ale mohou obsahovat terminály i neterminály v libovolné kombinaci.

Příklad

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