Detail práce

One-Sided Random Context Grammars

Disertační práce Student: Zemek Petr Akademický rok: 2014/2015 Vedoucí: Meduna Alexander, prof. RNDr., CSc.
Název česky
Jednostranné gramatiky s nahodilým kontextem
Jazyk
anglický
Stav
obhájeno
Obhajoba
12. září 2014
Ústav
Studijní program
Obor studia
Soubory
Klíčová slova

teorie formálních jazyků, řízené gramatiky, gramatiky s nahodilým kontextem, jednostranné gramatiky s nahodilým kontextem, povolující gramatiky, zakazující gramatiky, generativní síla, redukce, normální formy, nejlevější derivace, zobecněné verze, LL verze

Abstrakt

Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem. Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu.

Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu.

Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky.

Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.

Citace
ZEMEK, Petr. One-Sided Random Context Grammars. Brno, 2014. Disertační práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2014-09-12. Vedoucí práce Meduna Alexander. Dostupné z: https://www.fit.vut.cz/study/phd-thesis/238/
BibTeX
@PHDTHESIS{FITPT238,
    author = "Petr Zemek",
    type = "Diserta\v{c}n\'{i} pr\'{a}ce",
    title = "One-Sided Random Context Grammars",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2014,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/phd-thesis/238/"
}
Nahoru