Uniform Generation of languages by scattered context grammars

• Autorzy: Meduna A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

uniform rewriting; permutations; scattered context grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 3
• Strony: 231--235
• Opis fizyczny: bibliogr. 4 poz.

Twórcy

autor

Meduna A.

• Department of Computer Science and Engineering Brno University of Technology Bozetechova 2, Brno 61266 Czech Republic