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

• 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.

Publikace