Detail výsledku
Scattered Context in Formal Languages
The present thesis studies theoretical properties of scattered context grammars. The research is focused on four main areas. First, it examines the conditions under which erasing productions can be removed form a scattered context grammar. Second, four modifications of scattered context grammars are introduced and studied. Specifically, the considered modifications involve scattered context grammars with non-context-free components, derivations limited to the first n nonterminals, leftmost derivations, and, finally, derivations in which either the maximal or the minimal number of nonterminals is rewritten in every derivation step. Next, the thesis studies generators of sentences in which every sentence is enriched with a sequence of productions used during its generation. Canonical and reduced generators of this kind are discussed. Finally, several applications of scattered context grammars to natural language description and processing are presented.
formal language theory, scattered context grammars, generative power, descriptional complexity, erasing productions, canonical derivations, linguistics
@misc{BUT67032,
author="Jiří {Techet}",
title="Scattered Context in Formal Languages",
year="2008",
pages="123",
publisher="Faculty of Information Technology BUT",
address="Brno"
}