1.1 Formální jazyky
Abeceda
Abeceda (značíme \(\Sigma\)) je konečná množina prvků, které nazýváme symboly abecedy.
Řetězec
Řetězec (slovo) nad abecedou je každá konečná posloupnost symbolů abecedy.
- \(\varepsilon\) – prázdný řetězec, prázdná posloupnost symbolů,
- \(\Sigma^*\) – množina všech řetězců (včetně prázdného) nad abecedou \(\Sigma\),
- \(\Sigma^+\) – množina všech neprázdných řetězců nad abecedou \(\Sigma\), tedy \(\Sigma^* = \Sigma^+ \cup \{\varepsilon\}\).
Zřetězení
Zřetězení je operace spojující dva řetězce. Pokud máme dva řetězce \(x\) a \(y\), pak připojením řetězce \(y\) za řetězec \(x\) získáme řetězec \(x \cdot y = xy\). Platí, že \(x\varepsilon = \varepsilon x = x\) a také \(x(yz) = (xy)z\) (asociativita). Ale obecně \(xy \neq yx\) (neplatí komutativita).
Délka řetězce
Délka řetězce \(x\), značíme \(|x|\), je nezáporné celé číslo udávající počet symbolů řetězce. Délka prázdného řetězce je nulová – tj. \(|\varepsilon| = 0\). Řetězec, který sestává právě z \(k\) výskytů symbolu \(a\), budeme symbolicky značit \(a^k\). Například: \(a^3 = aaa, a^0 = \varepsilon\).
Definice 1.5 (Reverze řetězce)
Reverze řetězce
Reverze řetězce \(x\) (značíme \(x^R\)) je řetězec \(x\) zapsaný zprava doleva.
Podřetězec
Řekneme, že \(x\) je podřetězcem (substring) \(w\), pokud \(w = vxu \land u, v, w, x \in \Sigma^*\). Jinými slovy platí, že před a za \(x\) ve \(w\) mohou být libovolné řetězce.
Podsekvence
Řetězec \(x = x_1 \dots x_n\) je podsekvencí \(w\), pokud \(w = u_1x_1u_2 \dots x_nu_{n+1} \land u_1, \dots, u_{n+1} \in \Sigma^* \land x_1, \dots, x_n \in \Sigma \land x, w \in \Sigma^*\). Jinými slovy platí, že ve \(w\) mohou být před, za i uvnitř \(x\) (mezi jednotlivými symboly) libovolné řetězce.
Formální jazyk
Formální jazyk nad abecedou \(\Sigma\) (značíme \(L\)) je libovolná podmnožina množiny všech možných řetězců nad danou abecedou – tj. \(L \subseteq \Sigma^*\).
Pozor! Rozlišujeme následující jazyky:
- \(L = \{\varepsilon\}\) … neprázdný jazyk s jedním prvkem, kterým je prázdný řetězec (\(\varepsilon\))
- \(L = \{\} = \emptyset\) … prázdný jazyk
Operace nad jazyky
Operace nad jazyky jsou obdobné jako operace s klasickými množinami:
- sjednocení jazyků: \(L_1 \cup L_2 = \{x : x \in L_1 \lor x \in L_2\}\)
- průnik jazyků: \(L_1 \cap L_2 = \{x : x \in L_1 \land x \in L_2\}\)
- rozdíl jazyků: \(L_1 \setminus L_2 = \{x : x \in L_1 \land x \notin L_2\}\)
- doplněk jazyka: \(\overline{L} = \{x \in \Sigma^* : x \notin L\}\)
- součin (zřetězení) jazyků: \(L_1 \cdot L_2 = \{w : w = x \cdot y \land x \in L_1 \land y \in L_2\}\)
- iterace jazyka: \(L^* = \bigcup_{n=0}^{\infty} L^n\), kde \(L^n = L \cdot L^{n-1}\) pro \(n \in \mathbb{N}\) a \(L^0 = \{\varepsilon\}\)