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 práce
anglický
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ů.

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

Ústav
Studijní program
Soubory
Stav
obhájeno
Obhajoba
12. září 2014
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