Název: Koncové větné formy a jejich aplikace
Překlad názvu: Final Sentential Forms and Their Applications
Autoři: Kožár, Tomáš ; Kövári, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2022
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
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. Context-free grammars are one of the most used formal models in formal language theory. They have many useful applications, but for many applications, they lack expressive power. We introduce a final language F . When a sentential form of the context-free grammar G belongs to the F , it becomes a final sentential form. By the erasion of the nonterminals from the final sentential forms, we receive a language of G finalized by F , L(G,F) . We prove that for each recursively enumerable language L , there exists context-free grammar G , such that L = L(G,F) , with F = { w#reversal(w) | w is from {0,1}*}, where reversal(w) is a reversal of w . When a regular language is used as F , no increase in generative power compared to context-free grammars is achieved. We show multiple applications of the final sentential forms in the fields of the linguistics and bioinformatics.
Klíčová slova: Cocke-Younger-Kasami; CYK; formal grammars; minimal linear grammars; recursively enumerable languages; sentential forms; Cocke-Younger-Kasami; CYK; formálne gramatiky; minimálne lineárna gramatiky; rekurzívne vyčísliteľné jazyky; vetné formy

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/207458

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-504999


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce