On representing RE languages by one-sided internal contextual languages

Ehrenfeucht Andrzej and Mateescu Alexandru and Păun Gheorghe and Rozenberg Grzegorz and Salomaa Arto: On representing RE languages by one-sided internal contextual languages. In: Acta cybernetica, (12) 3. pp. 217-233. (1996)

[thumbnail of cybernetica_012_numb_003_217-233.pdf]
Cikk, tanulmány, mű

Download (847kB) | Preview


In this paper we prove that each recursively enumerable language L can be written in the form L — cutd(L' fl R), where L' is a language generated by a one-sided internal contextual grammar witli context-free choice, R is a regular language, and cutd is the operation which removes the prefix bounded by the special symbol d, which appears exactly once in the strings for which cutd is defined. However, the context-free choice sets are always deterministic linear languages of a very simple form. Similar representations can be obtained using one-sided contextual grammars with finite choice and with erased or with erasing contexts.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1996
Volume: 12
Number: 3
ISSN: 0324-721X
Page Range: pp. 217-233
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38501/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 232-233. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 14:25
URI: http://acta.bibl.u-szeged.hu/id/eprint/12557

Actions (login required)

View Item View Item