Detail práce
O vymazávacích pravidlech v řízených gramatikách
V této práci je diskutován vliv vymazávacích pravidel na generativní sílu řízených gramatik, což je velký otevřený problém teorie řízeného přepisování. Tato práce studuje možnost odstranění vymazávacích pravidel z těchto gramatik tak, že shromažďuje aktuální výsledky na toto téma a přináší novou podmínku, nazvanou k-limitované vymazávání, která zaručuje, že jsme bez vlivu na generovaný jazyk schopni odstranit všechna vymazávací pravidla z libovolné bezkontextové gramatiky řízené regulárním jazykem splňující tuto podmínku. Tento výsledek je částečným řešením výše zmíněného problému. Mimoto je prezentován nový algoritmus k odstranění vymazávacích pravidel z bezkontextových gramatik, který nepotřebuje předurčovat tzv. epsilon-neterminály (na rozdíl od standardního algoritmu používaného v učebnicích). V závěru je zhodnocen přínos těchto výsledků pro syntaktickou analýzu.
bezkontextová gramatika, řízené gramatiky, bezkontextová gramatika řízená regulárním jazykem, odstraňování vymazávacích pravidel, limitované vymazávání
Fučík Otto, doc. Dr. Ing. (UPSY FIT VUT), člen
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT), člen
Květoňová Šárka, Ing., Ph.D. (UIFS FIT VUT), člen
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT), člen
Mišovič Milan, prof. RNDr., CSc. (Mendelu), člen
@mastersthesis{FITMT9183,
author = "Petr Zemek",
type = "Diplomov\'{a} pr\'{a}ce",
title = "O vymaz\'{a}vac\'{i}ch pravidlech v \v{r}\'{i}zen\'{y}ch gramatik\'{a}ch",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2010,
location = "Brno, CZ",
language = "czech",
url = "https://www.fit.vut.cz/study/thesis/9183/"
}