Název:
Alternativní gramatické transformace
Překlad názvu:
Alternative Transformations of Grammars
Autoři:
Havel, Martin ; Křivka, Zbyněk (oponent) ; Meduna, Alexandr (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2023
Jazyk:
eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng][cze]
Tato práce poskytuje alternativní algoritmus pro odstranění epsilon-pravidel z E0S gramatik. Oproti standardnímu způsobu odstranění epsilon-pravidel ve většině gramatik podobných E0S gramatikám, jako bezkontextové gramatiky, tato metoda nevyžaduje predeterminizaci symbolů, které generují prázdné řetězce. Navržený algoritmus je formálně verifikován. V implementační kapitole práce, navržený algoritmus je implementován a použitelnost algoritmu na E0S gramatikách je demonstrována. Na závěr je algoritmus vyhodnocen a jsou nastíněny dvě otevřené oblasti.
This thesis provides an alternative algorithm for the removal of erasing rules from E0S grammars. As opposed to the standard way of eliminating erasing rules in most E0S-like grammars, such as context-free grammars, this method does not require predetermination of symbols that derive the empty string. The proposed algorithm is formally verified. In the application chapter of the thesis, the proposed algorithm is implemented, and the applicability of the algorithm to E0S grammars that work in a semi-parallel way is demonstrated. In the conclusion of the thesis, the algorithm is evaluated and two open problems are formulated.
Klíčová slova:
context-free grammars; E0S grammars; elimination of erasing rules.; Formal languages; bezkontextové gramatiky; E0S gramatiky; eliminace epsilon-pravidel.; Formální jazyky
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/213203