Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 5

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: scattered context grammars

Sortuj według:

Ogranicz wyniki do:

Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Křivka Zbyněk, Meduna Alexander

Fundamenta Informaticae

2021

Vol. 179, nr 4

361--384

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Scattered context grammars generating sentences followed by derivation tree

Meduna A., Židek S.

Theoretical and Applied Informatics

2011

Vol. 23, No. 2

97-106

Propagating scattered context grammars are used to generate sentences of languages defined by scatterd context grammars followed by the strings corresponding to the derivation trees. It is proved that for every language defined by a scattered context grammar, there exists a propagating scattered context grammar whose language consists of original language sentences followed by strings representing their derivation trees.

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

Masopust T.

Fundamenta Informaticae

2010

Vol. 99, nr 4

473-480

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.

On Descriptional Complexity of Partially Parallel Grammars

Masopust T., Meduna A.

Fundamenta Informaticae

2008

Vol. 87, nr 3-4

407-415

This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Uniform Generation of languages by scattered context grammars

Meduna A.

Fundamenta Informaticae

2001

Vol. 45, nr 3

231-235

The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y1Ľym u, where u is a terminal word and each yi is a permutation of either of two equally long words, z1 E {A, B,C}* and z2 E {A, B, D}*, where A, B, C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y1...ym.