Formální jazyky

Formální jazyk představuje jakési zobecnění pojmu jazyk, na který jsme zvyklí z běžného života.

Základní pojmy

Formální jazyk si můžeme pro začátek představit jako běžný jazyk, například čeština. Z čeho se skládá takový jazyk? Skládá se ze slov, které dále spojujeme do nějakých vět. Věty nás zajímat nebudou, budou nás zajímat pouze slova. Z čeho se skládají slova? Z písmen abecedy. Abecedou tak začneme.

Abeceda je libovolná neprázdná množina. Prvky abecedy nazýváme symboly. Pokud je řeč o češtině, pak to bude klasická česká abeceda zahrnující jak malá, tak velká písmena plus varianty písmen s háčky a čárky. Pokud bychom nechtěli popisovat češtinu, ale například čísla, měli bychom v abecedě všech deset číslic. Abecedu často značíme symbolem $\Sigma$.

Slovem, nebo také řetězem, rozumíme konečnou posloupnost symbolů z nějaké abecedy $\Sigma$. Pokud máme například abecedu $\Sigma=\left\{a,b,c,d,e,\dots, z\right\}$, pak slovem je například posloupnost „ahoj“ nebo „dobrman“, ale už ne „večer“ (nemáme tam písmeno „č“), „Honza“ (nemáme písmeno „H“) nebo „dobry den“ (nemáme mezeru). Délkou slova rozumím počet symbolů, ze kterých se slovo skládá.

Zřetězení slov: pokud máme nějaká dvě slova a = a₁a₂… a_n a b = b₁b₂… b_m, pak zřetězením slov vznikne slovo ab = a₁a₂… a_nb₁b₂… b_m. Příklad: zřetězením slov „ahoj“ a „dobrman“ vznikne slovo „ahojdobrman“. Zřetězení značíme buď kolečkem, tj. $a\circ b$, nebo ho neznačíme nijak a prostě slova zapíšeme za sebe bez speciálního symbolu pro zřetězení.

Prázdné slovo značíme $\varepsilon$ a značíme tak slovo, které má délku nula. Pokud zřetězeníme slovo a = a₁… a_n s prázdným slovem $\varepsilon$, získáme zpět slovo a. Tj. platí $a\circ\varepsilon=a$.

Uzávěr abecedy $\Sigma$ je množina všech slov, která jsme schopni vytvořit z abecedy $\Sigma$, včetně prázdného slova. Uzávěr značíme $\Sigma^\ast$. Pokud máme binární abecedu $\Sigma=\left\{0,1\right\}$, pak platí

$$ \Sigma^\ast=\left\{\varepsilon,0{,}1,01{,}10,11{,}011,101{,}110,\dots\right\} $$

Občas používáme ještě kladný uzávěr abecedy, což jsou opět všechna slova, která jsme schopni poskládat z abecedy, kromě prázdného slova. Kladný uzávěr značíme $\Sigma^+$ a platí $\Sigma^+=\Sigma^\ast\setminus\left\{\varepsilon\right\}$.

Příklady abeced

• Vrátíme se zpět k příkladu s češtinou. Každé české slovo nalezneme v uzávěru abecedy, která obsahuje malá a velká písmena a varianty s diakritikou (plus možná ještě spojovník “-“). Pokud k této abecedě přidáme ještě mezeru a interpunkční znaménka (čárka, tečka, vykřičník, otazník, …), získáme uzávěrem všechny věty, které jsme schopni v českém jazyce vytvořit. Samozřejmě součástí tohoto uzávěru budou i věty typu „sadflsf kasdf kagrjewičiážřčáščáýker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf“, které jsou ale stále smysluplnější než projevy Miloše Zemana.

• Pokud bude naše abeceda obsahovat všechny číslice $\Sigma=\left\{0, 1, \dots, 9\right\}$, pak v uzávěru budou všechna přirozená čísla — a ještě nějaká navíc. Budou tam totiž i čísla začínají nulou, např. 00054, nebo samotná nula a navíc tam ještě bude prázdné slovo, což samozřejmě není žádné číslo.

• Abeceda musí být neprázdná, takže nejmenší abeceda má alespoň jeden symbol. Například pro abecedu $\Sigma=\left\{!\right\}$ bychom získali uzávěr $\Sigma^\ast=\left\{\varepsilon, !, !!, !!!, !!!!, \dots\right\}$, tj. množinu slov, přičemž pro každé n∈ℕ₀ v uzávěru existuje slovo, které má n vykřičníků a žádné jiné slovo v uzávěru nebude.

• Nechť $\Sigma=\left\{qw,c\right\}$. Tohle je velmi zvláštní abeceda, protože obsahuje slovo qw. Toto značení se obvykle nepoužívá, protože je zmatené a divné, ale můžeme si to představit tak, že slepíme písmena „q“ a „w“ k sobě tak, že budou tvořit jeden znak. Potom můžeme vidět slovo „qw“ jako symbol „qw“. Pokud bychom z tohoto symbolu vytvořili slovo „qwcqw“, pak by toto slovo mělo délku tři — bylo by složeno ze symbolů „qw“, „c“ a „qw“. Moc často se s podobnými případy abeced nesetkáme, ale existují situace, kdy takové symboly skládající se z více symbolů, potřebujeme použít.

Formální jazyk

(Formální) jazyk nad abecedou $\Sigma$ je libovolná podmnožina $\Sigma^\ast$. Pro jazyk L nad abecedou $\Sigma$ tak platí $L\subseteq\Sigma^\ast$. Příklady jazyků:

• V předchozí části jsme si definovali abecedu číslic $\Sigma=\left\{0, 1, \dots, 9\right\}$. Uzávěrem jsou všechna slova tvořená jen číslicemi. Pokud dodáme pravidlo, že slovo nesmí začínat nulou a slovo nesmí být prázdné, získáme množinu přirozených čísel ℕ. Platí vztah $\mathbb{N}\subseteq\Sigma^\ast$, takže ℕ je jazykem nad abecedou $\Sigma$.

• Do předchozí množiny číslic můžeme ještě přidat znak minus “-“, takže $\Sigma=\left\{0, 1, \dots, 9, -\right\}$. Uzávěrem jsou všechna slova, která se skládají z číslic nebo znaménka minus. To ovšem znamená, že v uzávěru jsou i slova jako „12-84-“, „1-5-8“ nebo “-“. Jazyk celých čísel ℤ vytvoříme tak, že přidáme tři pravidla:

  • Znak minus se ve slově nevyskytuje vůbec nebo se vyskytuje na začátku slova.
  • První číslice ve slově nemůže být nula kromě slova „0“.
  • Každé slovo musí obsahovat alespoň jednu číslici.

  Tato množina popisuje množinu celých čísel a je to podmnožina množiny $\Sigma^\ast$ — je to tak jazyk nad abecedou $\Sigma$.

• Nechť $\Sigma=\left\{0,1\right\}$. Uzávěrem tak jsou všechna slova, která se skládají z nul a jedniček. Jazyk L nad toto abecedou můžeme definovat např. jako množinu všech slov, která mají právě tři jedničky. Můžeme být i kreativnější a můžeme říci, že jazyk L bude množina všech slov, které představují platný formát souboru docx (to co vyleze z Wordu).

• Zůstaneme u binární abecedy $\Sigma=\left\{0,1\right\}$. Každý řetězec znaků (běžných znaků, které máte na klávesnici) lze převést do binární podoby, tj. do nul a jedniček, a zase zpátky například pomocí ASCII tabulky (nebo přesněji — ASCII tabulka převádí znaky na čísla a čísla z desítkové soustavy lze převést na čísla v binární soustavě). Můžeme tak definovat jazyk všech slov, které odpovídají platnému emailu a stále to bude jazyk nad binární abecedou.

Zřetězení jazyků: zřetězit můžeme i abecedy. Definice bude podobná jako u kartézského součinu množin. Mějme dva jazyky L₁ a L₂. Jejich zřetězením $L_1\circ L_2$ získáme nový jazyk, který definujeme takto:

$$ L_1\circ L_2 = \left\{w_1\circ w_2,|,w_1\in L_1, w_2\in L_2\right\} $$

Tj. vezmeme všechna slova z jazyka L₁ a zřetězíme je se všemi slovy z jazyka L₂. Příklad: Nechť

\begin{eqnarray} L_1&=&\left\{0,1\right\}\\ L_2&=&\left\{a,b,ahoj\right\}\\ \end{eqnarray}

Pak platí:

\begin{eqnarray} L_1\circ L_2 &=& \left\{0a, 0b, 0ahoj, 1a, 1b, 1ahoj\right\}\\ L_2\circ L_1 &=& \left\{a0, a1, b0, b1, ahoj0, ahoj1\right\}\\ L_1\circ L_1 &=& \left\{00, 01, 10, 11\right\} \end{eqnarray}

Zatím jsme pro popis jazyků používali obyčejný jazyk, zkrátka jsme slovně popsali, jak má jazyk vypadat. To je ale velmi nepraktické, takže se zavádí formálnější způsob jak definovat nějaký jazyk. Prvním z nich je gramatika.