| Meno: | Ján
|
|---|
| Priezvisko: | Rosina
|
|---|
| Názov: | Nondeterminism in generative systems
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2021
|
|---|
| Kµúčové slová: | generative systems, determinism, nondeterminism, generative systems with endmarker
|
|---|
| Abstrakt: | This thesis has two main goals in the research of generative systems. The first one is to investigate the power of deterministic generative systems with endmarker for which we prove equality to the family of recursively enumerable languages. The second one is to define and study computational measures of nondeterminism in generative systems. We introduce two such measures. First of them measures the number of nondeterministic decisions in relation to the length of the derivation. For this measure we show that for an arbitrary recursively enumerable language there exists an equivalent generative system with
arbitrarily slowly increasing upper bound function of complexity. The second measure considers the dependency of the number of nondeterministic decisions on the length of the derived words. In the general case, for recursively enumerable languages, we obtain linear upper bound function with respect to the length of the words. For unary languages and language $\Sigma ^*$ we obtain logarthmic upper bound and upper bound function of recursive languages is related to the number of words of a given length belonging to a given language.
|
|---|