Thesis Details
Final Sentential Forms and Their Applications
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.
formal grammars, sentential forms, minimal linear grammars, recursively enumerable languages, Cocke-Younger-Kasami, CYK
Č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
@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/"
}