Ústav informačních systémů

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

Hlavní řešitel:Zemek Petr
Spoluřešitelé:Meduna Alexander, Vrábel Lukáš
Agentura:FRVŠ MŠMT
Kód:FR271/2012/G1
Začátek:2012
Konec:2012
Soubory: 
+Typ Jméno Název Vel. Změněn
iconPresentationsPrezentace12.2013-01-06 17:08:46
iconText.pdfStudijní Text768 KB2013-01-06 17:46:07
^ Vybrat vše
S vybranými:
Klíčová slova:teorie formálních jazyků, teoretická informatika, matematika
Anotace:
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.
Realizační výstupy:
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:

Publikace

2012MEDUNA Alexander, VRÁBEL Lukáš a ZEMEK Petr. An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets. In: DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems. Braga: Springer Verlag, 2012, s. 236-243. ISBN 978-3-642-31622-7. ISSN 0302-9743.
 VRÁBEL Lukáš. A New Normal Form for Programmed Grammars with Appearance Checking. In: Proceedings of the 18th Conference STUDENT EEICT 2012 Volume 3. Brno: Vysoké učení technické v Brně, 2012, s. 420-425. ISBN 978-80-214-4462-1.
 ZEMEK Petr. Normal Forms of One-Sided Random Context Grammars. In: Proceedings of the 18th Conference STUDENT EEICT 2012 Volume 3. Brno: Vysoké učení technické v Brně, 2012, s. 430-434. ISBN 978-80-214-4462-1.

Vaše IPv4 adresa: 54.81.163.254
Přepnout na IPv6 spojení

DNSSEC [dnssec]