Regulární gramatiky, regulární výrazy a konečné automaty

Gramatika G je čtveřice (N,Σ,P,S), kde:

N je konečná množina neterminálních symbolů (neterminálů).

Σ je konečná množina terminálních symbolů tak, že žádný symbol nepatří do N a Σ zároveň (jsou disjunktní).

P je konečná množina odvozovacích pravidel. Každé pravidlo je tvaru

"cokoli poskládaný ze všech možnejch symbolů na cokoli"; S je prvek z N nazývaný počáteční symbol.

Lineární gramatika = bezkontextová gramatika, která má nanejvýš jeden neterminál na pravé straně. Regulární gramatika je speciálním případem lineární gramatiky, kdy všechny neterminály jsou na levém konci/straně (levá lineární = levá regulární) nebo ekvivalentně pro pravou stranu.

Regulární gramatika – je to gramatika typu 3 = lineární, navíc převedená do regulárního tvaru (podle Chomského hierarchie). Pravidla těchto lineárních gramatik jsou omezena na jeden neterminál na levé straně. Pravá strana se u pravé regulární gramatiky skládá z jednoho terminálu (u lineární i z více), který může být následován jedním neterminálem, tedy:

kde X, Y jsou neterminály a w je řetězcem terminálů. Regulární gramatiky se také nazývají pravé lineární gramatiky. Obdobně se definují i levé regulární gramatiky, které obsahují pravidla typu:

Pravé a levé gramatiky jsou ekvivalentní. Jazyky generované regulárními (=lineárními) gramatikami jsou právě jazyky rozpoznatelné konečným automatem.

Lineární gramatika = má na pravé straně právě jeden neterminál

Regulární gramatika = gramatika, která popisuje regulární jazyk, přesně definovaný tvar pravidel (B -> a, B -> aC, B -> e pro pravou regulární gramatiku)

Regulární gramatika je tedy buď jen levá lineární gramatika nebo jen pravá lineární gramatika. Čistě lineární (levo-pravá) gramatika je pak taková gramatika, která sestává z pravých i levých pravidel současně.

A → wB or A → w.

S → Λ | aS | T

T → b | bT.

Recursively enumerable

Turing machine

Context-sensitive

Linear-bounded non-deterministic Turing machine

Context-free

Non-deterministic pushdown automaton

Regular

Finite state automaton

Regulární výrazy umožňují algebraické manipulace s regulárními množinami - umožňují vyjádření regulárních množin. Třída regulárních výrazů nad abecedou S je definována takto:

každé písmeno (symbol - znak) s Î S  je regulární výraz nad S

Daná množina je regulární množina nad S, právě když může být popsána vhodným regulárním výrazem nad S. Každý regulární výraz U popisuje jistou množinu Ũ slov nad S: Ũ Í S*

Regulární množiny se vhodně charakterizují přechodovými grafy. Přechodový graf T nad abecedou S je konečný orientovaný graf, jehož každá hrana je pojmenována jistým slovem w Î S* ;alespoň jeden uzel je počáteční.

Množinu všech slov akceptovaných konečným automatem A označíme Ã. Množina je regulární nad S právě když je akceptována vhodným automatem nad S

Regulární výraz je řetězec popisující celou množinu řetězců (slov), konkrétně regulární jazyk. Používají se nejčastěji v počítačových programech a skriptovacích jazycích pro vyhledávání a úpravu textu. V případě, že uživatel chce v textu vyhledat nějaký řetězec, který nezná přesně nebo který může mít více variant, může zadat regulární výraz, který postihne všechny chtěné varianty. Program tak nalezne všechny části textu, které danému výrazu odpovídají.

Každý z regulárních výrazů označuje jistý regulární jazyk.

Kleeneho teorém: Každý regulární výraz je převoditelný na konečný automat.

Konečné automaty

formálně je konečný automat definován jako uspořádaná pětice (S,Σ,P,s,F) , kde:

S je konečná množina stavů.

Σ (velké sigma) je konečná množina vstupních symbolů nazývaná abeceda.

P je tzv. přechodová funkce (též přechodová tabulka), formálně zobrazení δ: S ´ Σ ® S, popisující pravidla přechodů mezi stavy. Přechod je určen stavem ve kterém se automat nachází a symbolem, který přichází na vstup (nebo který je čten na vstupu) 

s je počáteční stav (s naleží S)

F je množina koncových (přijímacích) stavů (F je podmnožinou S)

Popis činnosti automatu: Na počátku se automat nachází v definovaném počátečním stavu. Dále v každém kroku přečte jeden symbol ze vstupu a přejde do stavu, který je dán hodnotou, která v přechodové tabulce odpovídá aktuálnímu stavu a přečtenému symbolu. Poté pokračuje čtením dalšího symbolu ze vstupu, dalším přechodem podle přechodové tabulky, atd. Podle toho, zda automat skončí po přečtení vstupu ve stavu, který patří do množiny koncových stavů, platí, že automat buď daný vstup přijal nebo nepřijal. Množina všech řetězců, který daný automat přijme, tvoří regulární jazyk.

Konečné automaty se dělí dále na deterministické (DKA, DFA) a nedeterministické (NKA, NFA). U deterministických automatů, každý stav má právě jeden možný přechod pro každý možný vstup. U nedeterministického automatu jsou navíc povoleny e-hrany a více hran z jednoho stavu pro stejný vstup => v jeden okamžik se NKA může nacházet ve více stavech současně. Existuje však algoritmus, který umožňuje libovolný NKA převést na o něco složitější DKA (nejhůře v exponenciálním čase, prakticky však řádově rychleji).

Jak určit zdali je nějaký jazyk možné rozpoznat regulárním výrazem (konečným automatem, regulární gramatikou)? K tomuto lze použít tzv. Pumping teorém [wiki] nebo česky [abclinuxu].

Teorém vlastně říká, že v dostatečně dlouhém slově w daného regulárního jazyka můžeme nalézt tři části — x, y a z, přičemž nejdůležitější část y může zahrnovat i celé slovo. Aby byl tento jazyk regulární, musí platit, že část y můžeme ze slova vyjmout, nebo jí libovolně zopakovat, a přitom stále zůstáváme v rámci stejného jazyka.
