Generative power and closure properties of Watson-Crick grammars

• Main Authors: Mohamad Zulkufli, Nurul Liyana, Turaev, Sherzod, Mohd Tamrin, Mohd Izzuddin, Messikh Azeddine, Azeddine
• Format: Article
• Language: English; English
• Published: Hindawi Publishing Corporation 2016
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://irep.iium.edu.my/52351/1/9481971.pdf; http://irep.iium.edu.my/52351/7/52351-Generative%20Power%20and%20Closure%20Properties%20of%20Watson-Crick%20Grammars-WOS.pdf; http://irep.iium.edu.my/52351/; https://www.hindawi.com/journals/acisc/2016/9481971/

We define WK linear grammars,as an extension of WK regular grammars with linear grammar rules,and WK context-free grammars, thus investigating their computational power and closure properties. We show that WK linear grammars can generate some context sensitive languages. Moreover, we demonstrate tha...