On representing RE languages by one-sided internal contextual languages
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 prefi...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
1996
|
| Sorozat: | Acta cybernetica
12 No. 3 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12557 |
| Tartalmi 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. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 217-233 |
| ISSN: | 0324-721X |