Matematické základy teorie formálních jazyků

S kolegou Lukášem Vrábelem jsme dokončili projekt, který jsme vypracovali v rámci získaného FRVŠ grantu za rok 2012. Týkal se matematických základů teorie formálních jazyků. O výsledky bych se chtěl podělit v následujícím příspěvku.

Co byla naším cílem

V současné době je na Fakultě informačních technologií Vysokého učení technického v Brně vyučována řada předmětů, jejichž jádro tvoří teorie formálních jazyků. V těchto předmětech však není prostor k vysvětlení matematických základů, na kterých teorie formálních jazyků, a potažmo celá teoretická informatika, stojí. Tyto základy by studentům měly dát povinné matematické prerekvizitní předměty, kterou jsou ovšem zaměřeny velice obšírně. Taktéž nevysvětlují návaznost a využití nabytých znalostí v dalších oblastech. Studenti si pak mnohdy neuvědomují fundamentální význam matematických konceptů a důležitost formálních zápisů.

Cílem tohoto projektu bylo vytvoření studijních podkladů, které studenty provedou základy matematiky v úzké návaznosti na teorii formálních jazyků. Názorně by jim měly ukázat využitelnost matematické notace a ozřejmit důvody použití rigorózních postupů. Důraz je kladen na osvětlení problematiky na příkladech a analogií z oblastí, které jsou studentům blízké (např. programovací jazyky).

Jelikož je většina literatury zabývající se formálními jazyky psána v angličtině, je naprosto nezbytné seznámit studenty s anglickou terminologií, a proto jsou výukové materiály vytvořeny v angličtině. Studenti se tak seznámí se současnou, ve světě používanou notací, což je připraví na práci ve špičkových týmech mimo Českou republiku, kde mohou být tyto znalosti požadovány.

Co jsme vyprodukovali

Projekt, včetně jeho výstupů, je prezentován na internetových stránkách fakulty, konkrétně na adrese

http://www.fit.vutbr.cz/~izemek/frvs2012
Zde je k dispozici jako doplňkový zdroj informací studentům všech předmětů, které se teoretickou informatikou zabývají (i mimo fakultu).

V rámci řešení projektu byly vypracovány následující výstupy:

• Studijní text. Anglicky psaný text, který studenty seznamuje s matematickými základy teorie formálních jazyků a teoretické informatiky jako takové. Učí je formálním zápisům, vysvětluje přínos matematiky a návaznost na teorii formálních jazyků. Formát i styl výkladu je uzpůsoben tomu, aby k pochopení textu bylo třeba minimum dodatečných materiálů.
• Prezentace k textu. Pět elektronických prezentací, které umožňují přednášejícímu projít se studenty některé obzvláště náročné pasáže ze studijního textu. Jejich hlavním cílem není nahrazení studijního textu, nýbrž usnadnění práce přednášejícímu. Konkrétně se jedná o následující prezentace:
  • Sets. Základy teorie množin, především co to jsou množiny, jak je lze zapisovat, vztahy mezi množinami, speciální množiny a operace nad množinami.
  • Sequences, Relations, and Functions. Jsou vysvětleny posloupnosti, relace a funkce.
  • Finite Automata. Tato prezentace se zabývá formální definicí konečného automatu, relace přechodu, výpočtu a přijímaného jazyka. Jsou využity koncepty z předchozích dvou prezentací.
  • Closures. Vysvětlení konceptu uzávěru relací, který slouží pro snadnější definici výpočtu prováděného konečným automatem.
  • Mathematical Statements and Their Proofs. Zdůvodnění, proč jsou důkazy v matematice důležité, ukázka obecného tvaru matematických tvrzení, typy tvrzení a jejich důkazy. 
• Bonusové prezentace. Bylo vytvořeno sedm bonusových elektronických prezentací diskutujících pokročilá témata z moderní teorie formálních jazyků, které v současné době nejsou součástí ani doktorských předmětů. Prezentace jsou založeny na dalších článcích řešitelů tohoto projektu. Konkrétně se jedná o následující prezentace:
  • Jumping Finite Automata. Modifikace konceptu konečného automatu, kdy automat po přečtení symbolu může skočit na jakékoliv místo na vstupní pásce.
  • On Nondeterminism in Programmed Grammars. Je diskutován vliv nedeterminismu na generativní sílu tzv. programovaných gramatik.
  • On Szilard Languages. V této prezentaci jsou zmíněny vlastnosti tzv. Szilardových jazyků pro různé typy gramatik.
  • Workspace Theorems for Regular-Controlled Grammars. Je prezentována podmínka, za které lze z každé tzv. gramatiky řízené regulárním jazykem odstranit vymazávací pravidla.
  • Converting Finite Automata to Regular Expressions. Jsou ukázány tři způsoby, jak lze převést konečný automat na ekvivalentní regulární výraz.
  • Lookahead k > 1 in LL and LR Translators. Je diskutován vliv počtu vstupních symbolů, které překladače vidí, na jejich generativní sílu.
  • One-Sided Random Context Grammars. Shrnutí známých poznatků o tzv. gramatikách s jednostranným nahodilým kontextem.