Sets of integers in different number systems and the Chomsky hierarchy

The classes of the Chomsky hierarchy are characterized in respect of converting between canonical number systems. We show that the relations of the bases of the original and converted number systems fall into four distinct categories, and we examine the four Chomsky classes in each of the four cases...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Katsányi István
Testületi szerző: Conference for PhD Students in Computer Science (2.) (2000) (Szeged)
Dokumentumtípus: Cikk
Megjelent: 2001
Sorozat:Acta cybernetica 15 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12667
Leíró adatok
Tartalmi kivonat:The classes of the Chomsky hierarchy are characterized in respect of converting between canonical number systems. We show that the relations of the bases of the original and converted number systems fall into four distinct categories, and we examine the four Chomsky classes in each of the four cases. We also prove that all of the Chomsky classes are closed under constant addition and multiplication. The classes RE and CS are closed under every examined operation. The regular languages axe closed under addition, but not under multiplication.
Terjedelem/Fizikai jellemzők:121-136
ISSN:0324-721X