Thesis Details

Final Sentential Forms and Their Applications

Master's Thesis Student: Kožár Tomáš Academic Year: 2021/2022 Supervisor: Meduna Alexander, prof. RNDr., CSc.
Czech title
Koncové větné formy a jejich aplikace
Language
English
Abstract

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

formal grammars, sentential forms, minimal linear grammars, recursively enumerable languages, Cocke-Younger-Kasami, CYK

Department
Degree Programme
Files
Status
defended, grade A
Date
17 June 2022
Reviewer
Committee
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT), člen
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT), člen
Peringer Petr, Dr. Ing. (DITS FIT BUT), člen
Smrčka Aleš, Ing., Ph.D. (DITS FIT BUT), člen
Veselý Vladimír, Ing., Ph.D. (DIFS FIT BUT), člen
Citation
KOŽÁR, Tomáš. Final Sentential Forms and Their Applications. Brno, 2022. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2022-06-17. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/24245/
BibTeX
@mastersthesis{FITMT24245,
    author = "Tom\'{a}\v{s} Ko\v{z}\'{a}r",
    type = "Master's thesis",
    title = "Final Sentential Forms and Their Applications",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2022,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/24245/"
}
Back to top