Ehrenfeucht Andrzej; Mateescu Alexandru; Păun Gheorghe; Rozenberg Grzegorz; Salomaa Arto: On representing RE languages by one-sided internal contextual languages. In: Acta cybernetica, (12) 3. pp. 217-233. (1996)
Előnézet |
Cikk, tanulmány, mű
cybernetica_012_numb_003_217-233.pdf Letöltés (847kB) | Előnézet |
Absztrakt (kivonat)
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.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 1996 |
| Kötet: | 12 |
| Szám: | 3 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 217-233 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38501/ |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Megjegyzések: | Bibliogr.: p. 232-233. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2016. okt. 15. 12:26 |
| Utolsó módosítás: | 2022. jún. 13. 14:25 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12557 |
 |
Tétel nézet |
