Bakalářská práce

Pokročilá internetová služba pro řešení rozhodnutelných problémů z oblasti bezkontextových jazyků

Advanced internet service for solving decidable problems for context-free languages

Daniel Pelíšek
Anotace

Cílem této práce je podstatně rozšířit existující internetovou službu pro převod bezkontextových gramatik do různých kanonických forem a zjištění izomorfismu dvou gramatik. Práce zahrnuje odstranění chyb aktuální aplikace, přidání nové funkcionality pro analýzu zadané bezkontextové gramatiky, převod gramatiky na zásobníkový automat prostřednictvím nedeterministické syntaktické analýzy a implementaci …více

Abstract

The thesis deals with creation an internet service for analysing context-free grammars and transformation into various canonical forms. The final application is able to detect whether given grammar is in any canonical form (and name reasons), is self-embedded, generates empty, final or infinite language and find examples of words generated by the grammar. The service has also implemented functionality …více

Zadání práce
Cílem práce je podstatně rozšířit a intenzivně otestovat existující internetovou službu, která umí porovnávat bezkontextové gramatiky na isomofirmus a také převádět gramatiky do různých normálních forem. V rámci práce budou odstraněny chyby a nedostatky stávající aplikace (např. předpoklad konkrétního uspořádání neterminálů při odstraňování levé rekurze). Služba by měla být rozšířena zejména o analýzu zadávaných gramatik (tj. detekce, zda je gramatika v nějaké normální formě a zdůvodnění proč není, zda generuje prázdný/konečný/nekonečný jazyk, zda má vlastnost sebevložení, nalezení příkladů slov generovaných gramatikou atd.). Dále bude přidáno generování nedeterministických syntaktických analyzátorů (včetně jejich výpočtů pro zadané slovo) pro zadané gramatiky. Bude také implementována deterministická analýza pomocí C-Y-K algoritmu a to tak, aby služba byla schopna vyhodnotit i odpovědníkové otázky na toto téma. Konečně bude zřízena administrátorská stránka služby, která umožní zapnout/vypnou logování přístupů a řešených úkolů a dočasné vypnutí služby či jejich částí. Nedílnou součástí práce je zátěžový test této služby (nalezení limitů) a její optimalizace pro rychlou odezvu.
Práce zkontrolována:
21. 5. 2013 14:21, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Jazyk práce
čeština čeština
Termín obhajoby
20. 6. 2013
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Jan Strejček, Ph.D., učo 3366
KTP FI MU

Oponent

prof. RNDr. Mojmír Křetínský, CSc., učo 631
KTP FI MU

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.
  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.
  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.
  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.
  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.