Since adenine pairs with thymine and guanine pairs with cytosine, this seems to imply that there's a trivial Regular Expression for DNA (i.e. it's trivially a Regular Language, which is Type 3 on the Chomsky hierarchy). With that said, is there a "less trivial" Regular Expression for DNA? Or, even better, is there a "deeper" grammatical structure for DNA, such as a Context-Free Grammar?
closed as primarily opinion-based by kmm, fileunderwater, David, mgkrebbs, Chris♦ Mar 2 '18 at 12:18
Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.
In truth DNA doesn't fit in the Chomsky hierarchy at all. DNA isn't a language, it is a complex molecule in a complex chemical environment. The fact that in many situations we can usefully abstract the structure of DNA as a string of four symbols should not obscure the underlying complexity. There is a simple code that describes the aminos acids encoded by triples of nucleotides, and some elements of a "grammar" in the structure of genes if you squint (start codons, stop codons, introns, and exons). But much of the function of DNA is stochastic and driven by the biophysics of the binding of RNA and protein molecules to DNA.