TY - JOUR
T1 - Static Watson-Crick context-free grammars
AU - Fong, Wan Heng
AU - Rahman, Aqilahfarhana Abdul
AU - Sarmin, Nor Haniza
AU - Turaev, Sherzod
N1 - Funding Information:
This research work is supported by Ministry of Education (MOE) and Research Management Centre (RMC), Universiti Teknologi Malaysia (UTM) through Research University Grant Vote No. 5F022 and UTM under Zamalah Scholarship
Funding Information:
This research work is supported by Ministry of Education (MOE) and Research Management Centre (RMC), Universiti Teknologi Malaysia (UTM) through Research University Grant Vote No. 5F022 and UTM under Zamalah Scholarship.
Publisher Copyright:
© 2019 iJOE.
PY - 2019
Y1 - 2019
N2 - Sticker systems and Watson-Crick automata are two modellings of DNA molecules in DNA computing. A sticker system is a computational model which is coded with single and double-stranded DNA molecules; while Watson-Crick automata is the automata counterpart of sticker system which represents the biological properties of DNA. Both of these models use the feature of Watson-Crick complementarity in DNA computing. Previously, the grammar counterpart of the Watson-Crick automata have been introduced, known as Watson-Crick grammars which are classified into three classes: Watson- Crick regular grammars, Watson-Crick linear grammars and Watson-Crick context-free grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick context-free grammar, which is a grammar counterpart of sticker systems that generates the double-stranded strings and uses rule as in context-free grammar, is introduced. The static Watson-Crick context- free grammar differs from a dynamic Watson-Crick context-free grammar in generating double-stranded strings, as well as for regular and linear grammars. The main result of the paper is to determine the generative powers of static Watson-Crick context-free grammars. Besides, the relationship of the families of languages generated by Chomsky grammars, sticker systems and Watson- Crick grammars are presented in terms of their hierarchy.
AB - Sticker systems and Watson-Crick automata are two modellings of DNA molecules in DNA computing. A sticker system is a computational model which is coded with single and double-stranded DNA molecules; while Watson-Crick automata is the automata counterpart of sticker system which represents the biological properties of DNA. Both of these models use the feature of Watson-Crick complementarity in DNA computing. Previously, the grammar counterpart of the Watson-Crick automata have been introduced, known as Watson-Crick grammars which are classified into three classes: Watson- Crick regular grammars, Watson-Crick linear grammars and Watson-Crick context-free grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick context-free grammar, which is a grammar counterpart of sticker systems that generates the double-stranded strings and uses rule as in context-free grammar, is introduced. The static Watson-Crick context- free grammar differs from a dynamic Watson-Crick context-free grammar in generating double-stranded strings, as well as for regular and linear grammars. The main result of the paper is to determine the generative powers of static Watson-Crick context-free grammars. Besides, the relationship of the families of languages generated by Chomsky grammars, sticker systems and Watson- Crick grammars are presented in terms of their hierarchy.
KW - Context-free grammar
KW - DNA computing
KW - Generative power
KW - Sticker systems
KW - Watson-Crick grammar
UR - http://www.scopus.com/inward/record.url?scp=85068115755&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068115755&partnerID=8YFLogxK
U2 - 10.3991/ijoe.v15i10.10878
DO - 10.3991/ijoe.v15i10.10878
M3 - Article
AN - SCOPUS:85068115755
SN - 2626-8493
VL - 15
SP - 65
EP - 76
JO - International journal of online and biomedical engineering
JF - International journal of online and biomedical engineering
IS - 10
ER -