Názov:Grammars With Energy and Finite Approximations of Languages
Vedúci:prof. RNDr. Branislav Rovan, PhD.
Kµúčové slová:Grammars With Energy, Monotone Sequences of Finite Languages, Sequences of Approximations, Distances on Languages
Abstrakt:The main goal of this thesis is to define the finite approximation of infinite languages, prove some useful properties of this formal definition, and introduce the distance measure on this construction. As the first step, we needed to modify the definition of grammars with energy from Janosk's thesis, allowing one-sided approximations of the given language. We define the monotone sequences of finite languages, which are used as sequences of approximations for a given language. We introduce operations on these sequences, and prove some of their properties. We also define the string and weak distance measure between monotone sequences of approximations. In this thesis we show how the strong and the weak distance measures behave, when we can obtain additional information about the monotone sequences being measured. Later we show how can grammars with energy generate sequences of approximations, and we introduce classes of sequences of approximations generated by grammars with energy. Finally, we show that under specific conditions the strong distance measure is related to the strict grammars with energy.

Súbory diplomovej práce: