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

Verzia z 16:04, 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:

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, t. j.: 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.: $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}$ Ak hovoríme

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

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

[1]

@@ Riadok 1: / Riadok 1: @@
-Vysvetlíme si základné pojmy (abeceda, symbol, reťazec, jazyk...), klasifikáciu gramatík a využitie formálnych jazykov a gramatík v praxi.
 {{Pojmová mapa}}
 == História ==
+[[Súbor:Turing_Machine_Model_Davey_2012.jpg|náhľad|251x251bod|Model Turingovho stroja, skonštruovaný Mike Daveyom, vystavený na Harvardovej univerzite v roku 2012.<ref>"A Turing Machine Overview" - Mike Davey (https://aturingmachine.com/)</ref>]]
 V 30-tych rokov 20. storočia britský matematik a logik [https://sk.wikipedia.org/wiki/Alan_Turing 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 [https://sk.wikipedia.org/wiki/Turingov_stroj Turingov stroj].
-[[Súbor:Turing Machine Model Davey 2012.jpg|náhľad|Model Turingovho stroja, skonštruovaný Mike Daveyom, vystavený na Harvardovej univerzite v roku 2012.<ref>"A Turing Machine Overview" - Mike Davey (https://aturingmachine.com/)</ref>]]
-{{Téma|Oblast=Kategória:Formálne jazyky a automaty|Poradie=10}}
+Otázkou bolo: dajú sa všetky problémy riešiť pomocou algoritmu?
-<references />
+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:
+=== 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, t. j.: 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.:<math display="block">V^* = \{ \ldots, a, b, c, \ldots, asdaf, asdafa, \ldots, \color{green}{mama}\color{black}, \ldots, xyzhrbbdfu \}</math>Ak hovoríme
 [[Kategória:Formálne jazyky a automaty]]