Detail práce

Final Sentential Forms and Their Applications

Diplomová práce Student: Kožár Tomáš Akademický rok: 2021/2022 Vedoucí: Meduna Alexander, prof. RNDr., CSc.
Název česky
Koncové větné formy a jejich aplikace
Jazyk práce
anglický
Abstrakt

Bezkontextové gramatiky sú jedny z najpoužívanejších formálnych modelov v teórii formálnych jazykov. Majú mnoho užitočných použití, no pre mnoho aplikácii nemajú dostatočnú vyjadrovaciu silu. Preto zavádzame koncový jazyk F. Keď vetná forma bezkontextovej gramatiky G patrí do jazyka F, stáva sa konečnou vetnou formou. Odstránením neterminálov z konečných vetných foriem získavame jazyk gramatiky G ukončený jazykom F, L(G,F). Dokazujeme, že pre každý rekurzívne vyčísliteľný jazyk existuje jazyk L(G,F), kde F = {w#reversal(w) | w patrí do {0,1}*} a reversal(w) je obrátené slovo w. Keď ako F použijeme regulárny jazyk, nedosiahneme žiadne zvýšenie vyjadrovacej sily oproti bezkontextovým gramatikám. Ukazujeme viacero aplikácii koncových vetných foriem v oblastiach lingvistiky a bioinformatiky.

Klíčová slova

formálne gramatiky, vetné formy, minimálne lineárna gramatiky, rekurzívne vyčísliteľné jazyky, Cocke-Younger-Kasami, CYK

Ústav
Ústav informačních systémů FIT VUT v Brně
Studijní program
Informační technologie a umělá inteligence, specializace Matematické metody
Soubory
Stav
obhájeno, hodnocení A
Obhajoba
17. června 2022
Oponent
Kövári Adam, Mgr.
Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.

Otázky u obhajoby
  1. Jaká je výpočetní složitost původní a modifikované verze algoritmu?
  2. Jak by se výsledky změnily, kdyby byl připojen jiný bezkontextový jazyk?
  3. Jaký byl implementační rozsah vaší práce?
  4. Jaké důkazové technicky jste používal ve vaší práci?
  5. Jak dlouho rozhodnutí o dotazu trvá?
Komise
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT), předseda
Češka Milan, doc. RNDr., Ph.D. (UITS FIT VUT), člen
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT), člen
Peringer Petr, Dr. Ing. (UITS FIT VUT), člen
Smrčka Aleš, Ing., Ph.D. (UITS FIT VUT), člen
Veselý Vladimír, Ing., Ph.D. (UIFS FIT VUT), člen
Citace
KOŽÁR, Tomáš. Final Sentential Forms and Their Applications. Brno, 2022. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2022-06-17. Vedoucí práce Meduna Alexander. Dostupné z: https://www.fit.vut.cz/study/thesis/24245/
BibTeX 
@mastersthesis{FITMT24245,
    author = "Tom\'{a}\v{s} Ko\v{z}\'{a}r",
    type = "Diplomov\'{a} pr\'{a}ce",
    title = "Final Sentential Forms and Their Applications",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2022,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/24245/"
}

Závěrečné práce

Nahoru