Static Watson-Crick context-free grammars

Wan Heng Fong, Aqilahfarhana Abdul Rahman, Nor Haniza Sarmin, Sherzod Turaev

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)65-76
Number of pages12
JournalInternational journal of online and biomedical engineering
Issue number10
Publication statusPublished - 2019
Externally publishedYes


  • Context-free grammar
  • DNA computing
  • Generative power
  • Sticker systems
  • Watson-Crick grammar

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Static Watson-Crick context-free grammars'. Together they form a unique fingerprint.

Cite this