Úvod do formálnych jazykov: Rozdiel medzi revíziami

Verzia z 17:02, 25. september 2024

História

V 30-tych rokov 20. storočia britský matematik a logik Alan Turing skúmal abstraktné výpočtové zariadenie, ktoré malo všetky schopnosti dnešných počítačov. Takéto zariadenie sa nazýva Turingov stroj.

Otázkou bolo: dajú sa všetky problémy riešiť pomocou algoritmu?

O Turingovom stroji v kontexte formálnych jazykov a automatov hovoríme že je to "automat" - teda, zariadenie ktoré dokáže automaticky previesť nejaký vstup na výstup. Každý automat pritom využíva určité pravidlá, podľa ktorých generuje výstup - gramatiku.

Základné pojmy

Predtým, ako môžme pochopiť čo je presne automat a ako sa dá matematiky alebo schematicky vyjadriť jeho princíp fungovania, si musíme vysvetliť základné pojmy. Našťastie, veľa z týchto pojmov už poznáme pretože ich využívame v každodennom živote, a teda znamenajú presne to, čo si pod nimi predstavujeme. Ale možno z trochu iného hľadiska - toho matematického:

Abeceda

Abeceda je ľubovoľná konečná množina symbolov. Označujeme ju písmenom $V$ . Napríklad: $V = {a, b, c, d, \dots, x, y, z}$ je množina, ktorá obsahuje všetky malé písmená (symboly) anglickej abecedy.

Symboly nemusia byť iba písmená, ale aj číslice a dokonca iné špeciálne znaky. To znamená, že aj nasledujúca abeceda je platná: $V = {-, Ψ, Θ, ℵ, ♡, ⅁, ♠}$ .

Slovo

Slovo $w$ je ľubovoľná konečná postupnosť symbolov z abecedy $V$ . Dĺžku slova $w$ (teda, počet znakov v slove) označujeme ako $| w |$ . Napríklad: $\begin{array}{lcl} w & = & m a m a \\ | w | & = & 4 \end{array}$

Prázdne slovo

Prázdne slovo označujeme gréckym písmenom ε. Je to slovo, ktoré má nulovú dĺžku: $| ϵ | = 0$ . Predstav si to ako prázdny reťazec v programovacom jazyku: "" // reťazec nulovej dĺžky: je to nič. Aj keď sa na prvý pohľad zdá že to nedáva zmysel a tento symbol je nepotrebný, neskôr pri príkladoch zistíme, že spĺňa dôležitú funkciu pri popisovaní gramatík.

Jazyk

Jazyk označujeme pomocou písmena $L$ (ako z anglického Language). Jedná sa o ľubovoľnú podmnožinu množiny $V^{*}$ všetkých slov nad nejakou abecedou $V$ . To znamená, že ak $V^{*}$ obsahuje všetky možné kombinácie symbolov z abecedy $V$ ktorých je nekonečne veľa, tak táto podmnožina obsahuje iba tie vybrané symboly ktoré sú platné pre daný jazyk (dávajú zmysel, teda: spĺňajú pravidlá danej gramatiky).

Predstav si to, ako keby existovali všetky možné kombinácie písmen, bez ohľadu na to či by tie slová dávali zmysel alebo nie. To by predstavovala množina $V^{*}$ , napríklad:

$V^{*} = {\dots, a, b, c, \dots, a s d a f, a s d a f a, \dots, m a m a, \dots, x y z h r b b d f u}$

Tak potom podmnožina - jazyk $L$ - bude obsahovať iba tie kombinácie ktoré obsahujú platné slová pre ten jazyk. Napríklad: mama.

↑ "A Turing Machine Overview" - Mike Davey (https://aturingmachine.com/)

Gramatika vo formálnych jazykoch »

[1] "A Turing Machine Overview" - Mike Davey (https://aturingmachine.com/)

[1]

@@ Riadok 12: / Riadok 12: @@
 === Abeceda ===
-Abeceda je ľubovoľná konečná množina symbolov. Označujeme ju písmenom <math>V</math>.
+Abeceda je ľubovoľná konečná množina symbolov. Označujeme ju písmenom <math>V</math>. Napríklad: <math>V = \{ a, b, c, d, \ldots, x, y, z \}</math> je množina, ktorá obsahuje všetky malé písmená (symboly) anglickej abecedy.
+Symboly nemusia byť iba písmená, ale aj číslice a dokonca iné špeciálne znaky. To znamená, že aj nasledujúca abeceda je platná: <math>V = \{ -, \Psi, \Theta, \aleph, \heartsuit, \Game, \spadesuit \}</math>.
+=== Slovo ===
+Slovo <math>w</math> je ľubovoľná konečná postupnosť symbolov z abecedy <math>V</math>. Dĺžku slova <math>w</math> (teda, počet znakov v slove) označujeme ako <math>|w|</math>. Napríklad:<math display="block">\begin{array}{lcl}
+w   & = & mama \\
+|w| & = & 4
+\end{array}</math>
+==== Prázdne slovo ====
+Prázdne slovo označujeme gréckym písmenom '''ε'''. Je to slovo, ktoré má nulovú dĺžku: <math>|\epsilon| = 0</math>. Predstav si to ako prázdny reťazec v programovacom jazyku: <code>"" // reťazec nulovej dĺžky: je to nič</code>. Aj keď sa na prvý pohľad zdá že to nedáva zmysel a tento symbol je nepotrebný, neskôr pri príkladoch zistíme, že spĺňa dôležitú funkciu pri popisovaní gramatík.
 === Jazyk ===
 Jazyk označujeme pomocou písmena <math>L</math> (ako z anglického '''''L'''anguage''). '''Jedná sa o ľubovoľnú podmnožinu množiny <math>V^*</math> všetkých slov nad nejakou abecedou <math>V</math>.''' To znamená, že ak '''<math>V^*</math>'''obsahuje všetky možné kombinácie symbolov z abecedy '''<math>V</math>''' ktorých je nekonečne veľa, tak táto podmnožina obsahuje iba tie vybrané symboly ktoré sú platné pre daný jazyk (dávajú zmysel, teda: spĺňajú pravidlá danej gramatiky).
-Predstav si to, ako keby existovali všetky možné kombinácie písmen, bez ohľadu na to či by tie slová dávali zmysel alebo nie. To by predstavovala množina <math>V^*</math>, napr.:
+Predstav si to, ako keby existovali všetky možné kombinácie písmen, bez ohľadu na to či by tie slová dávali zmysel alebo nie. To by predstavovala množina <math>V^*</math>, napríklad:
 <math display="block">V^* = \{ \ldots, a, b, c, \ldots, asdaf, asdafa, \ldots, \color{green}{mama}\color{black}, \ldots, xyzhrbbdfu \}</math>
-Tak potom podmnožina - jazyk <math>L</math> - bude obsahovať iba tie kombinácie ktoré obsahujú platné slová pre ten jazyk. Napríklad: ''mama''.
+Tak potom podmnožina - jazyk <math>L</math> - bude obsahovať iba tie kombinácie ktoré obsahujú platné slová pre ten jazyk. Napríklad: ''<span style="color: green;">mama</span>''.
 [[Kategória:Formálne jazyky a automaty]]
 <references />
 {{Téma|Oblast=Kategória:Formálne jazyky a automaty|Poradie=10}}