Matematický základ

Množina je soubor prvků, chápaných jako celek. Může být určena výčtem prvků, který uzavřeme do složených závorek: {a,b,c}. Na pořadí prvků nezáleží a každý z nich je v mno­žině jenom jednou. Další způsob zápisu nekonečných či hodně velkých množin je zvolení určité základní (univerzální) množiny a upřesňujících podmínek, které udávají charakteristickou vlastnost prvků množiny. Jednotlivé části se oddělí středníkem „;“ a vše se uzavře do složených závorek: M = {x ∈ D; ν(x)} Prázdnou množinu {} označujeme symbolem ∅.

Posloupnost na rozdíl od množiny určuje i pořadí prvků. Prvky se mohou opakovat, liší se vždy minimálně svým pořadím v posloupnosti. Posloupnost určujeme výčtem uzavřeným do kulatých závorek: (a,c,c). Podle počtu prvků je posloupnost uspořádaná dvojice, trojice,…, n-tice.

Posloupnost znaků nazýváme řetězec -slovo a zapisujeme jej bez kulatých závorek a bez od­dě­lo­va­če prvků. Jen jednotlivé prvky zapíšeme za sebe: aab.

Abeceda a slovo

Abeceda Σ je konečná množina znaků. Obvykle předpokládáme, že není prázdná. Prvky abecedy nazýváme znaky (symboly).

Slovo nad danou abecedou (v dané abecedě) je libovolně dlouhá, konečná posloupnost zna­ků (symbolů) z nějaké abecedy Σ.

Prázdné slovo „“ neobsahuje žádný symbol. Značí se ε

Příklad 1:
Abeceda: Σ = {a, b}
Příklady slov v abecedě Σ: abaab, baa, aa, ab

Příklad 2:
Abeceda: Σ = {0, 1}
Příklady slov v abecedě Σ: 110, 011, 101

Ve smyslu proměnných budou malá písmena ze začátku anglické abecedy (a, b, c,…) s pří­pad­nými indexy představovat znaky zkoumané abecedy. Jako proměnné pro slova budeme obvykle používat malá písmena z konce abecedy (u, v, w, x, y, z).

Délka slova

Délka slova je počet znaků ve slově. Délku slova w označujeme |w|. Prázdné slovo ε má délku 0. To znamená, že |ε| = 0. Výrazem |w|_a označujeme počet výskytů symbolu a ve slově w.

Příklad 1:
Slovo u = abaab, má délku |u| = 5.

Příklad 2:
Slovo u = abaab, má počet výskytů symbolu „a“ |u|_a = 3.

Příklad 3:
Slovo εab  má délku |εab| = 2.

Zřetězení slov

Zřetězení slov u = a₁a₂…a_n a v = b₁b₂…b_n označujeme u·v, a definujeme je

Symbol „·“ je možné vypouštět. Lze tedy na­psat abb·ab = abbab. Zřetězením slov abb a ab vznikne slovo abbab.

Zřetězení je asociativní, tj. pro libovolná tři slova u, v a w platí

což znamená, že při zápisu více zřetězení můžeme vypouštět závorky a psát například

místo

Zřetězení není komutativní, tj. obecně pro dvojici slov u a v neplatí rovnost

Příklad:

Zjevně pro libovolná slova v a w platí:

Pro libovolné slovo w  a ε také platí, že:

Jazyk

Množinu všech slov nad konečnou abecedou Σ (tvořených symboly z abe­ce­dy Σ) označu­jeme Σ*. Patří mezi ně také prázdné slovo ε. Množinu všech neprázdných slov v abecedě Σ* označujeme Σ⁺.

Množinu všech slov z abecedy Σ = {0, 1} bychom vypsali takto:

ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 1000,…

Formální jazyk, stručně jazyk nad abecedou Σ, je libovolná množina slov v abecedě Σ, tedy libovolná podmnožina Σ*:

Počet slov jazyka L značíme svislicemi: |L|. Prázdný jazyk {} (neobsahující žádná slova) označujeme ∅. Platí pro něj, že má délku 0, což zapisujeme |∅| = 0. Jazyk obsahující pouze prázdné slovo {ε} má délku jedna, tj. platí |ε| = 1. Oba jsou jazyky nad jakoukoliv abecedou.

Množina všech slov nad konečnou abecedou je nekonečná. Slova v dané abecedě můžeme totiž přirozeně uspořádat: nejprve podle délky a v rámci stejné délky podle abecedy, tj. podle zvoleného uspořádání na prvcích abecedy. Tak jsou slova seřazena do jedné pos­loup­nos­ti, ve které je lze po řadě očíslovat přirozenými čísly.

Poznámka: Problém ale je, že podle předchozí definice mají mít slova konečnou délku. Bývá uváděno, že slova mohou mít délku konečnou i když libovolně velkou. Zde je na místě odlišit množiny potenciálně nekonečné od aktuálně nekonečných.

Je výhodné (a velmi potřebné) mít možnost definovat složitější jazyk prostřednictvím dvou jednodušších a nějaké operace, která je spojí. Protože jsou jazyky definovány jako množiny, můžeme na to používat běžné množinové operace.

Poznámka: Při operacích nad jazyky předpokládáme, že jazyky, se kterými operaci provádíme, používají tutéž abecedu Σ. Pokud abecedy Σ₁, Σ₂ jazyků L₁, L₂; stejné nejsou, můžeme výsledný jazyk chápat jako jazyk s abecedou Σ₁ ᑌ Σ₂.

Sjednocení jazyků

Sjednocení jazyků L₁ ᑌ L₂ je jazyk tvořený slovy, která patří buď do jazyka L₁ nebo do jazyka L₂ (nebo do obou).

Dále můžeme definovat nové operace speciálně pro práci s jazyky. Např. je to zřetězení jazyků (odvozené od zřetězení slov) či iterace (tedy opakované řetězení):

Zřetězení jazyků

Zřetězení jazyků L₁, L₂ je jazyk L₁ · L₂ = {uv ; u∈L₁, v∈L₂}, jenž tedy obsahuje všechna slova, která lze rozdělit na dvě části, z nichž první je z jazyka L₁ a druhá z jazyka L₂. Jinak řečeno jazyk všech slov, která začínají slovem z L₁ a pokračují slovem z L₂.

Zřetězení jazyků L₁ a L₂ označujeme L₁ · L₂.

Příklad:
L₁ = {abb, ba}
L₂ = {a, ab, bbb}
Jazyk L₁ · L₂ obsahuje slova:
abb·a  abb·ab  abb·bbb  ba·a  ba·ab  ba·bbb.
(Aby bylo možné pochopit na první pohled způsob, jakým byla slova utvořena, nebylo u tohoto příkladu vynecháno označení zřetězení.) Více možností zřetězení slov již není.

Operace zřetězení jazyků obecně není komutativní.
Například zřetězení jazyků L₂ · L₁ z předchozího příkladu obsahuje slova:
a·abb  a·ba  ab·abb  ab·ba  bbb·abb  bbb·ba

Iterace jazyka

Iterace jazyka L, značená L*, je jazyk všech slov, která lze rozdělit na několik částí, z nichž každá patří do jazyka L. Do L* zařazujeme ε (chápané jako zřetězení 0 slov). Iterace jazyka je tedy jazyk tvořený slovy vzniklými zřetězením všech slov z jazyka L.

Induktivní definice iterace pro libovolné k ≥ 0:

Iterace jazyka L je jazyk

L* = L⁰ ᑌ L¹ ᑌ L² ᑌ L³ ᑌ …,

kde

L⁰ = {ε},

L^k+1 = L^k · L  pro k ≥ 0.

Pro snazší pochopení lze definici zapsat následujícím způsobem:

L* = {ε} ᑌ L ᑌ L² ᑌ L³ ᑌ L⁴ ᑌ L⁵ ᑌ …,

kde

L² = L · L
L³ = L · L · L
L⁴ = L · L · L · L
L⁵ = L · L · L · L · L
….

Operací iterace je definitivně matematicky zaveden jazyk jako aktuálně nekonečná množina.

Příklad 1: Pokud L = {aa, b}, pak L³
obsahuje slova:
aa·aa·aa   aa·aa·b  aa·b·aa  aa·b·b  b·aa·aa  b·aa·b  b·b·aa  b·b·b

Příklad 2: L = {aa, b}
L* = {ε, aa, b, aaaa, aab, baa, bb, aaaaaa, aaaab, aabaa, aabb,…}

Zatímco Σ* je množina všech slov nad abecedou Σ, L* je množina všech slov v jazyce L. To znamená ne úplně všech slov, které je možné vytvořit v abecedě Σ, ale jenom těch, které lze sestavit v jazyce L. (V abecedě totiž, chceme-li, lze sestavit všechna slova v dané abecedě, v jazyce to již možné není.)

Podle definice zavede iterace L* do množiny slov jazyka prázdné ε slovo jako „zřetězení nula slov z L“. Zřetězením nula slov vznikne prázdné slovo ε také v prázdném jazyce

Jak zapsat jazyk s velkým nebo nekonečným počtem slov

Jazyk coby množinu slov definujeme obvykle formálním zápisem. U konečných jazyků stačí tato slova vypsat, ale u jazyků s nekonečným počtem slov to nejde. Jeden ze způsobů jak zapsat nekonečný jazyk jsme si ukázali v předchozím textu. Je to pomocí iterace, která vytváří libovolně dlouhá slova jakéhokoliv jazyka.

Příklad:
L = ǀ* je množina slov (tedy jazyk) nad abecedou Σ = {ǀ}, v jazyce jsou všechna slova nad touto abecedou skládající se pouze ze symbolů ǀ a prázdného znaku ε:

L = {ε, ǀ, ǀǀ, ǀǀǀ, ǀǀǀǀ, ǀǀǀǀǀ,…}

Další způsob zápisu nekonečných či hodně velkých jazyků je zápis pomocí množin. Uvede se formální předpis a po oddělovači (to je obvykle středník, svislice nebo dvojtečka) upřesňující podmínky jak mají vypadat slova jazyka. V zápisu často používáme proměnné, které určují vazbu mezi formálním předpisem a upřesňujícími podmínkami:

L = {aⁿbⁿ;n ≥ 0}.

L je v tomto případě množina všech slov nad abecedou Σ = {a, b} takových, že první polovina slova obsahuje pouze symboly a, druhá pouze symboly b a symbolů a a b je vždy stejný počet. To jest:

L = {ε, ab, aabb, aaabbb, aaaabbbb,…}.

Proměnná, která váže formální předpis s upřesňujícími podmínkami je n.