Vědy 2. Regulární jazyky a bezkontextové jazyky. Popis těchto jazyků pomocí automatů a gramatik, vlastnosti regulárních a bezkontextových jazyků.
PREVIOUS
0.1 Jazyky - úvod
0.1.1 Abeceda
Konečnou neprázdnou množinu Σ budeme nazývat abecedou. Prvky množiny Σ nazýváme symboly, písmeny apod.
0.1.2 Slovo nad abecedou
Pro danou abecedu Σje slovo nad Σ libovolná konečná posloupnost prvků abecedy Σ. Tedy např. pro Σ = {a, b} jsou aab, b, bbaba slova nad Σ.
Prázdné slovo, značíme je ε , je posloupnost, která neobsahuje ani jeden symbol.
0.1.3 Délka slova
Je dáno slovo nad abecedou Σ. Délka slova je rovna délce posloupnosti, tj. počtu symbolů, které se ve slově nacházejí. Délku slova u značíme |u|.
Tedy, délka slova aab je rovna 3, délka b je 1, délka prázdného slova ε je 0.
0.1.4 Zřetězení slov
Je dána abeceda Σ. Pro dvě slova u, v nad abecedou Σ definujeme operaci zřetězení takto: Je-li u= a 1 a 2 … a n a v= b 1 b 2 … b k , pak
u ⋅ v= a 1 a 2 … a n b 1 b 2 … b k .
Často znak pro operaci zřetězení vynecháváme; píšeme tedy uv místo přesnějšího u ⋅ v .
Zřetězení slov je asociativní operace na množině všech slov nad danou abecedou, prázdné slovo ε je neutrální prvek této operace.
Σ ★ , Σ + . Označíme Σ ★ množinu všech slov nad abecedou Σ.(Tj. prázdné slovo patří do Σ ★ ) Pak Σ ★ spolu s operací zřetězení tvoří monoid, jehož neutrálním prvkem je prázdné slovo ε .
Označíme Σ + množinu všch neprázdných slov nad abecedou Σ .(Tj. Σ + = Σ ★ ∖ { ε } .) Pak Σ ★ spolu s operací zřetězení tvoří pologrupu.
Zřetězení slov není komutativní. Např. pro u=aab a v=b je uv=aabb , ale vu=baab .
Pro libovolná slova u a v nad stejnou abecedou platí:
| uv | =| u | +| v | .
Je-li u slovo nad abecedou Σ , pak můžeme opakování slova n-krát zapsat zjednodušeně jako uuuu...u= u n . Přesněji:
u 0 = ε , u i+1 =u u i pro každé i .
0.1.5 Podslovo
Je dáno slovo u. Řekneme, že slovo w je podslovem slova u, jestliže existují slova x, y taková, že
u=xwy.
0.1.6 Prefix slova
Je dáno slovo u. Řekneme, že slovo w je prefix slova u, jestliže existuje slovo y takové, že
u=wy.
0.1.7 Jazyk nad abecedou
Je dána abeceda Σ. Jazyk L nad abecedou Σ je libovolná množina slov, tj. L ⊆ Σ ★ .
Je-li Σ abeceda, pak množina všech slov Σ ★ je spočetná. Jazyků, jako podmnožin spočetné množiny, je víc - nespočetně mnoho.
0.2 Deterministické konečné automaty
0.2.1 Použití
Konečné automaty se používají v různých oborech. Jako příklady můžeme uvést překladače, dále se používají při zpracování přirozeného jazyka, pří návrzích hardwaru.
Zhruba řečeno, konečný automat obsahuje konečnou množinu stavů Q, konečnou množinu vstupů Σ, přechodovou funkci δ a počáteční stav q 0 . V některých případech ještě i množinu výstupních symbolů Y a výstupních funkcí.
0.2.2 Příklad 1
Uvažujme zjednodušený příklad automatu na kávu. Automat přijímá mince 1 Kč, 2 Kč a 5 Kč. Automat vydává jediný druh kávy, káva stojí 7 Kč. Automat na tlačítko s vrátí nevyužité peníze. Tento příkad uvedeme podrobněji.
Zde Q = {0,1,2,3,4,5,6}, Σ = {1,2,5,s}, Y = {K,0,1,2,3,4,5,6}, přechodová a výstupní funkce jsou dány následující tabulkou:
V prvním sloupci jsou stavy, ve kterých se automat může nacházet, v prvním řádku jsou vstupní symboly. V řádku odpovídajícím stavu q a sloupci se vstupen a je dvojice(nový stav, výstup).(K znamená kávu, číslo udává vrácené peníze).
1
2
5
s
0
1/0
2/0
5/0
0/0
1
2/0
3/0
6/0
0/1
2
3/0
4/0
0/K
0/2
3
4/0
5/0
1/K
0/3
4
5/0
6/0
2/K
0/4
5
6/0
0/K
3/K
0/5
6
0/K
1/K
4/K
0/6
0.2.3 Stavový diagram
Kromě tabulky, můžeme konečný automat zadat též stavovým diagramem.
PREVIOUS
0.1 Jazyky - úvod
0.2 Deterministické konečné automaty