Original title: Koncové větné formy a jejich aplikace
Translated title: Final Sentential Forms and Their Applications
Authors: Kožár, Tomáš ; Kövári, Adam (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2022
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: Cocke-Younger-Kasami; CYK; formálne gramatiky; minimálne lineárna gramatiky; rekurzívne vyčísliteľné jazyky; vetné formy; Cocke-Younger-Kasami; CYK; formal grammars; minimal linear grammars; recursively enumerable languages; sentential forms

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/207458

Permalink: http://www.nusl.cz/ntk/nusl-504999


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses