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