Abecedy a slova

• Abeceda (\(\Sigma\)) je konečná množina symbolů, což mohou být písmena, čísla nebo jiné znaky. Abeceda musí obsahovat alespoň jeden prvek.
• Řetězec (slovo) je posloupnost symbolů z této abecedy.
• Délka řetězce (kolik má symbolů) se značí \(|\alpha|\).
• Prázdný řetězec neobsahuje žádné symboly a značí se \(\varepsilon\), jeho délka je 0.
• Počet výskytů určitého znaku (například a) v řetězci α se značí jako #a(α).
• Reverzní (opačné) slovo \(a^R\) je slovo, které vznikne, když zapíšeš symboly slova α v opačném pořadí. Říká se tomu také zrcadlový obraz.
  • Například, pokud \(\alpha = a_1...a_n\), pak \(\alpha^R = a_n...a_1\).
  • Když obrátíš reverzní slovo zpět, dostaneš původní slovo: \((\alpha^R)^R = \alpha\).
  • Pro prázdný řetězec ε platí, že jeho reverzní obraz je stále prázdný: \(\varepsilon^R = \varepsilon\).
• Podslovo \(\beta\) je část slova \(\alpha\). To znamená, že \(\beta\) se nachází někde uvnitř slova \(\alpha\).
  • Předpona (prefix) je podslovo na začátku slova \(\alpha\).
  • Přípona (sufix) je podslovo na konci slova \(\alpha\).

Řetězení

Zřetězení (neboli spojení či konkatenace) dvou řetězců je proces, kdy vezmeš jeden řetězec a připojíš k němu druhý. Například pro řetězce α a β spojíš oba za sebe a získáš nový řetězec.

Vlastnosti zřetězení

• Délka spojeného řetězce je součet délek obou původních řetězců.
  • \(|\alpha.\beta| = |\alpha| + |\beta|\)
• Spojením slova s prázdným slovem vznikne původní slovo
  • \(\alpha.\varepsilon = \varepsilon.\alpha = \alpha\)
• Jedno slovo můžeme \(n\) krát zopakovat za sebou. To nazýváme \(n\)-násobné zřetězení a označuje se jako \(\alpha^n\).
  • Například \((abc)^3\) = \((abc).(abc).(abc) = (abcabcabc)\).
  • Pro \(n = 0\) je výsledek prázdné slovo \(\alpha^0 = \varepsilon\)
• Řetězení slova je asociativní, to znamená, že nezáleží, co zřetězíme první a co druhý, ve výsledku je to stejný.
  • \(\alpha . \beta . \gamma = (\alpha . \beta) . \gamma = \alpha . (\beta . \gamma)\)
• Řetězení není komutativní. Jinak řečeno, záleží na pořadí spojovaných slov.
  • \(\alpha . \beta \not= \beta . \alpha\)

Uzávěr abecedy

• Uzávěr abecedy (\(\Sigma^*\)) je množina všech možných slov, které lze vytvořit z abecedy \(\Sigma\) (to jsou všechny možné kombinace jejích symbolů, včetně prázdného slova).
• Pozitivní uzávěr (\(\Sigma^+\)) je stejná věc jako "klasický" uzávěr, ale neobsahuje prázdné slovo.
• Uzávěry jsou všechny možné způsoby, jak můžeš spojit symboly z abecedy libovolněkrát.
  • Tím vznikne spočetná množina.
  • Spočetná množina je taková, jejíž prvky můžeš spočítat, jako přirozená čísla (1, 2, 3…).
  • Spočetná množina může být i nekonečná.