Watson-Crick linear grammars
In this paper, we define Watson-Crick linear grammars ex- tending Watson-Crick regular grammars [9] with linear rules, and study their generative power. We show that Watson-Crick linear grammars can generate some context-sensitive languages. Moreover, we establish that the family of Watson-Crick re...
| Main Authors: | , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/43973/ http://irep.iium.edu.my/43973/ http://irep.iium.edu.my/43973/1/Watson_Crick_Linear_Grammar.pdf http://irep.iium.edu.my/43973/3/WKLinearGrammars_%281%29.pdf |
| Summary: | In this paper, we define Watson-Crick linear grammars ex-
tending Watson-Crick regular grammars [9] with linear rules, and study their generative power. We show that Watson-Crick linear grammars can generate some context-sensitive languages. Moreover, we establish that the family of Watson-Crick regular languages proper subset of the family of Watson-Crick linear languages but it is not comparable with the family of linear languages.
|
|---|