# Generative Power and Closure Properties of Watson-Crick Grammars

Authors: Nurul Liyana Mohamad Zulkufli; Sherzod Turaev; Mohd Izzuddin Mohd Tamrin; Azeddine Messikh
Journal: Applied Computational Intelligence and Soft Computing
 (2016)

---

## Abstract

We defineWK linear grammars, as an extension of WK regular grammars with linear grammar rules, andWK 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 that the family of WK regular languages is the proper subset of the family of WK linear languages, but it is not comparable with the family of linear languages. We also establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations.


---

## Body

## 1. Introduction

DNA computing appears as a challenge to design new types of computing devices, which differ from classical counterparts in fundamental way, to solve wide spectrum of computationally intractable problems. DNA (deoxyribonucleic acid) is double-stranded chain of nucleotides, which differ by their chemical bases that areadenine (A),guanine (G),cytosine (C), andthymine (T), and they are paired as A-T, C-G according to theWatson-Crick complementary as it is illustrated in Figure 1 [1]. Themassive parallelism, another fundamental feature of DNA molecules, allows performing millions of cut and paste operations simultaneously on DNA strands until a complete set of new DNA strands performing are generated. These two features give high hope for the use of DNA molecules and DNA based biooperations to develop powerful computing paradigms and devices.Figure 1
The structure of DNA strand.Since a DNA strand can be interpreted as a double strand sequence of symbols, the DNA replication and synthesize processes can be modeled using methods and techniques of formal language theory.Watson-Crick (WK) automata [2], one of the recent computational models abstracting the properties of DNA molecules, are finite automata with two reading heads, working on complete double-stranded sequences where characters on corresponding positions from the two strands of the input are related by a complementarity relation similar to the Watson-Crick complementarity of DNA nucleotides. The two strands of the input are separately read from left to right by heads controlled by a common state. Several variants have been introduced and studied in recent papers [3–7].WK regular grammars [8], a grammar counterpart of WK automata, generate double-stranded strings related by a complementarity relation as in a WK automaton but use rules as in a regular grammar. The approach of using formal grammars in the study of biological and computational properties of DNA molecules by formal grammars is a new direction in the field of DNA computing: we can introduce powerful variants of WK grammars, such as WK linear, WK context-free, and WK regulated grammars, and use them in the investigation of the properties of DNA structures and also in DNA applications in food authentication, gene disease detection, and so forth. In this paper, we introduceWK linear grammars and study the generative capacity in the relationship of Chomsky grammars.Further, as a motivation, we show synthesis processes, for instance, in DNA replication (Figure2) can be simulated by derivations in WK grammars. The replication of DNA begins at the origin(s). The double strand then separated by proteins, producing bubble-like shape(s). The synthesis of new strands using the parental strands as templates starts from the origins and proceeds in the 5
′ to 3
′ direction of both strands [1].Figure 2
Synthesis process in bacterial DNA replication.This synthesis process in general can be seen as astring generation. The enzymes responsible for the synthesizing, DNA polymerases, cannot initiate the process by themselves but can only add nucleotides to an existing RNA chain. This chain is calledprimer which is produced by the enzyme primase. From the grammar perspective, the primase can be interpreted as the start symbol S. After the primer has been connected to the parental strand, one of the synthesizing enzymes, called DNA polymerase III, continues to add nucleotides one by one to the primer and are complemented with the parental strand. The synthesis finishes with replacing RNA primer with DNA nucleotides using the enzyme DNA polymerase I and joining with DNA ligase. Again, from the grammar perspective, DNA polymerase I and polymerase III act as production rules in the grammar, specially, DNA ligase resembles to aterminal production (see Figure 3).Figure 3
The simulation of a synthesis process with a derivation.The paper is organized as follows. In Section2, we give some notions and definitions from the theories of formal languages and DNA computing needed in the sequel. In Section 3, we define WK grammars and languages generated by these grammars. Section 4 is devoted to the study of the generative capacity of WK regular and linear grammars. In Section 5, we investigate the closure properties of WK grammars. Furthermore, we show the application of WK grammars in the analyses of DNA structures and programming language structures in Section 6. As the conclusion, we discuss open problems and interesting future research topics related to WK grammars in Section 7.


## 2. Preliminaries

We assume readers are familiar with formal languages theory and automata. Readers are referred to [3, 9–11].Throughout this paper we use the following notations. Let∈ be the belonging relationship of an element to the corresponding set and ∉ indicates its negation. The symbol ⊆ indicates the inclusion while ⊂ notes the proper inclusion. The notations ∅, |
A
|, and 2
A denote the empty set, the cardinality of a set A, and the power set of A, respectively. When Σ is an alphabet (a finite set of symbols), the set of all finite strings is denoted by Σ
∗, while Σ
+ shows similar meaning without including empty strings (we use λ for empty string). The length of a string a
∈
Σ
∗ is shown by |
a
|. A language is a subset L
⊆
Σ
∗.Next we recall some terms regarding the closure properties of languages. Theunion of two languages, L
1
∪
L
2, is the set of strings including the elements contained in both sets of L
1 and L
2. Theconcatenation of two languages is yielded by lining two strings from both languages which is shown by (1)
L
1
L
2
=
a
b
∣
a
∈
L
1
,
b
∈
L
2
.TheKleene-star closure is the closure under the Kleene ∗ operation, the set of all possible strings in L including the empty string. Themirror image of a word a
=
a
1
a
2
⋯
a
n is a
R
=
a
n
⋯
a
2
a
1
. For language L, its mirror image is (2)
L
R
=
a
R
∣
a
∈
L
.Asubstitution is a mapping s
:
Σ
∗
→
T
∗ where s
(
λ
)
=
λ and s
(
a
1
,
a
2
)
=
s
(
a
1
)
s
(
a
2
) for a
1
,
a
2
∈
Σ
∗. The substitution for a language L
⊆
Σ
∗; that is, s
(
L
) is the union of s
(
y
), where y
∈
L. A substitution s is calledfinite if its length |
s
(
a
)
| is finite for each a
∈
Σ. Amorphism is a substitution where its length is 1.AChomsky grammar is defined by G
=
(
N
,
T
,
S
,
P
) where N is the set ofnonterminal symbols and T is the set ofterminal symbols, and N
∩
T
=
∅. S
∈
N is thestart symbol while P
⊆
(
N
∪
T
)
∗
N
(
N
∪
T
)
∗
×
(
N
∪
T
)
∗ is the set ofproduction rules. We write α
→
β indicating the rewriting process of the strings based on the production rules (
α
,
β
)
∈
P. The term x
directly derives
y is written as x
⇒
y when (3)
x
=
a
1
α
a
2
,
y
=
a
1
β
a
2for some production rules α
→
β
∈
P. A grammar generates alanguage defined by (4)
L
G
=
w
∈
T
∗
:
S
⟹
∗
w
.According to the forms of production rules, grammars are classified as follows. A grammarG
=
(
N
,
T
,
S
,
P
) is called(i)
context-sensitive if each production has the form u
1
A
u
2
→
u
1
u
u
2, where A
∈
N, u
1
,
u
2
,
∈
(
N
∪
T
)
∗, and u
∈
(
N
∪
T
)
+;
(ii)
context-free if each production has the form A
→
u, where A
∈
N and u
∈
(
N
∪
T
)
∗;
(iii)
linear if each production has the form A
→
u
1
B
u
2 or A
→
u, where A
,
B
∈
N and u
1
,
u
2
,
u
∈
T
∗;
(iv)
right-linear if each production has the form A
→
u
B or A
→
u, where A
,
B
∈
N and u
∈
T
∗;
(v)
left-linear if each production has the form A
→
B
u or A
→
u, where A
,
B
∈
N and u
∈
T
∗.A right-linear and left-linear grammars are calledregular.The families of languages generated by these grammars areR
E
G, L
I
N, C
F, and C
S, respectively. The families of recursive enumerable languages are denoted by R
E while the families of finite languages are denoted by F
I
N. Thus the next relation holds [11].Theorem 1 (Chomsky hierarchy).
Consider(5)
F
I
N
⊂
R
E
G
⊂
L
I
N
⊂
C
F
⊂
C
S
⊂
R
E
.We recall the definition of a finite automaton. Afinite automaton (FA) is a quintuple M
=
(
Q
,
V
,
q
0
,
F
,
δ
), where Q is the set ofstates, q
0
∈
Q is theinitial state, and F
⊆
Q is set offinal states. Meanwhile V is an alphabet and δ
:
Q
×
V
→
2
Q is called thetransition function. The set (language) of all strings accepted by M is denoted by L
(
M
). We denote the family of languages accepted by finite automata by F
A. Then, F
A
=
R
E
G (see [11]).Next, we cite some basic definitions and results of Watson-Crick automata.The key feature of WK automata is thesymmetric relation on an alphabet V; that is, ρ
⊆
V
×
V. In this paper, for simplicity, we use the form u
/
v to mention the elements (
u
,
v
) in the set of all pairs of strings V
×
V (which we choose to write as [
V
/
V
]), and, instead of V
∗
×
V
∗, we write V
∗
/
V
∗.Watson-Crick domain is the set of well-formed double-stranded strings (molecules) (6)
W
K
ρ
V
=
V
V
ρ
∗
=
a
b
:
a
,
b
∈
V
,
a
,
b
∈
ρ
.
W
K
ρ
+
(
V
) holds the similar meaning without including λ. We write (7)
a
1
b
1
a
2
b
2
⋯
a
n
b
n
∈
W
K
ρas [
u
/
v
] where theupper strand is u
=
a
1
a
2
⋯
a
n and thelower strand is v
=
b
1
b
2
⋯
b
n. Note that when the elements in the upper strand are complemented and have the same length with the lower strand, (8)
u
v
=
u
v
.A Watson-Crick finite automaton (WKFA) is 6-tuple(9)
M
=
Q
,
V
,
q
0
,
F
,
δ
,
ρ
,where Q, V, q
0, and F are the same as a FA. Meanwhile the transition function δ is (10)
δ
:
Q
×
V
∗
V
∗
⟶
2
Q
,where δ
(
q
,
u
/
v
) is not an empty set only for finitely many triples (
q
,
u
,
v
)
∈
Q
×
V
∗
×
V
∗. Similar to FA, we can write the relation in transition function q
2
∈
δ
(
q
1
,
u
/
v
) as a rewriting rule in grammars; that is, (11)
q
1
u
v
⟶
u
v
q
2
.We describe the reflexive and transitive closure of → as →
∗. The language accepted by a WKFA M is (12)
L
M
=
u
:
u
v
∈
W
K
ρ
V
,
q
0
u
v
⟶
∗
u
v
q
,
w
h
e
r
e
q
∈
F
.The family of languages accepted is indicated by W
K
F
A. It is shown in [10, 12] that (13)
R
E
G
⊂
W
K
F
A
⊂
C
S
.


## 3. Definitions

In this section we slightly modified the definition of Watson-Crick regular grammars introduced in [8] in order to extend the concept to linear grammars and context-free grammars.Definition 2.
A Watson-Crick (WK) grammarG
=
(
N
,
T
,
S
,
P
,
ρ
) is called(i)
regular if each production has the form (14)
A
⟶
u
v
B
or
A
⟶
u
v
,
whereA
,
B
∈
N and u
/
v
∈
T
∗
/
T
∗;
(ii)
linear if each production has the form (15)
A
⟶
u
1
v
1
B
u
2
v
2
or
A
⟶
u
v
,
whereA
,
B
∈
N and u
1
/
v
1
,
u
2
/
v
2
,
u
/
v
∈
T
∗
/
T
∗;
(iii)
context-free if each production has the form (16)
A
⟶
α
,
whereA
∈
N and α
∈
(
N
∪
(
T
∗
/
T
∗
)
)
∗.Definition 3.
LetG
=
(
N
,
T
,
ρ
,
S
,
P
) be a WK linear grammar. We say that x
∈
(
N
∪
T
∗
/
T
∗
)
∗ directly derives y
∈
(
N
∪
T
∗
/
T
∗
)
∗, denoted by x
⇒
y, iff (17)
x
=
u
1
v
1
A
u
2
v
2
,
y
=
u
1
v
1
u
3
v
3
B
u
4
v
4
u
2
v
2
or
y
=
u
1
v
1
u
v
u
2
v
2
,where A
,
B
∈
N, u
i
,
v
i
∈
T
∗
/
T
∗, i
=
1,2
,
3,4, and(18)
A
⟶
u
3
v
3
B
u
4
v
4
,
A
⟶
u
v
∈
P
.Definition 4.
LetG
=
(
N
,
T
,
ρ
,
S
,
P
) be a WK context-free grammar. We say that x
∈
(
N
∪
T
∗
/
T
∗
)
∗ directly derives y
∈
(
N
∪
T
∗
/
T
∗
)
∗, denoted by x
⇒
y, if and only if (19)
x
=
u
1
v
1
A
u
2
v
2
,
y
=
u
1
v
1
α
u
2
v
2
,where A
,
B
∈
N, u
i
,
v
i
∈
T
∗
/
T
∗, i
=
1,2
,
3,4, and A
→
α
∈
P.Remark 5.
We use a common notion “Watson-Crick grammars” referring to any type of WK grammars.Definition 6.
The language generated by a WK grammar is a quintupleG  which is defined as (20)
L
G
=
u
:
u
v
∈
W
K
ρ
T
,
S
⟹
∗
u
v
.


## 4. Generative Power of Watson-Crick Grammars

In this section, we establish results regarding the computational power of WK grammars.


### 4.1. A Normal Form for Watson-Crick Linear Grammars

Next, we define1-normal form for WK linear grammars and show that, for every WK linear grammar G, there is an equivalent WK linear grammar G
′ in the normal form; that is, L
(
G
)
=
L
(
G
′
).Definition 7.
A linear WK grammarG
=
(
N
,
T
,
ρ
,
P
,
S
) is said to be in the 1-normal form if each rule in P of the form (21)
A
⟶
u
1
v
1
B
u
2
v
2
or
A
⟶
u
1
v
1
,where |
u
i
|
≤
1, |
v
i
|
≤
1, i
=
1,2, and A
,
B
∈
N.Lemma 8.
For every WK linear grammarG, there exists an equivalent WK linear grammar G
′ in the 1-normal form.Proof.
LetG
=
(
N
,
T
,
ρ
,
S
,
P
) be a WK linear grammar. Let(22)
A
⟶
a
11
⋯
a
1
m
1
b
11
⋯
b
1
n
1
B
a
2
m
2
⋯
a
21
b
2
n
2
⋯
b
21be a production in P where m
1
>
1, m
2
>
1, n
1
>
1, or n
2
>
1. Without loss of generality, we assume that m
1
≥
n
1 and m
2
≥
n
2. Then, we define the following sequence of right-linear and left-linear production rules: (23)
A
⟶
a
11
b
11
A
11
r
,
A
11
r
⟶
a
12
b
12
A
12
r
⋮
A
1
n
1
-
1
r
⟶
a
1
n
1
b
1
n
1
A
1
n
1
r
,
A
1
n
1
r
⟶
a
1
n
1
+
1
λ
A
1
n
1
+
1
r
⋮
A
1
m
1
-
1
r
⟶
a
1
m
1
λ
A
1
m
1
r
,
A
1
m
1
r
⟶
A
21
r
a
21
b
21
,
A
21
r
⟶
A
22
r
a
22
b
22
⋮
A
1
n
2
-
1
r
⟶
A
2
n
2
r
a
2
n
2
b
2
n
2
,
A
2
n
2
r
⟶
A
2
n
2
+
1
r
a
2
n
2
+
1
λ
⋮
A
2
m
2
-
1
r
⟶
a
2
m
2
λ
,where A
1
j
r, 1
≤
j
≤
m
1, and A
2
j
r, 1
≤
j
≤
m
2
-
1, are new nonterminals.
Let(24)
r
:
A
⟶
a
1
a
2
⋯
a
m
b
1
b
2
⋯
b
n
∈
P
,where m
>
1 or n
>
1. Without loss of generality, we assume that m
≥
n. Then, we define the following sequence of right-linear production rules: (25)
A
⟶
a
1
b
1
A
1
r
,
A
1
r
⟶
a
2
b
2
A
2
r
,
A
n
-
1
r
⟶
a
n
b
n
A
n
r
,
A
n
r
⟶
a
n
+
1
λ
A
n
+
1
r
⋮
A
m
-
1
r
⟶
a
m
λ
,where A
i
r, 1
≤
i
≤
m
-
1, are new nonterminals.
We construct a WK linear grammarG
′
=
(
N
∪
N
′
,
T
,
ρ
,
S
,
P
∪
P
′
), where P
′ consists of productions defined above for each A
→
u
1
/
v
1
B
u
2
/
v
2
∈
P with |
u
1
|
>
1, |
v
1
|
>
1, |
u
2
|
>
1, or |
v
2
|
>
1 and A
→
u
/
v
∈
P with |
u
|
>
1 or |
v
|
>
1. Then, it is not difficult to see that, in every derivation, productions in the form of (22) and (24) in G can be replaced by the sequences of productions (23) and (25) in G
′ and vice versa. Thus, L
(
G
)
=
L
(
G
′
).


### 4.2. The Generative Power

The following results immediately follow from the definition of WK grammars.Lemma 9.
The following inclusions hold:(26)
W
K
R
E
G
⊆
W
K
L
I
N
,
L
I
N
⊆
W
K
L
I
N
,
C
F
⊆
W
K
C
F
.Next, we show that WK grammars can generate non-context-free languages:(27)
a
n
c
n
b
n
:
n
≥
1
,
a
n
b
m
c
n
d
m
:
n
,
m
≥
1
,
w
c
w
:
w
∈
a
,
b
∗
.Example 10.
LetG
1
=
(
{
S
,
A
,
B
}
,
{
a
,
b
,
c
}
,
{
(
a
,
a
)
,
(
b
,
b
)
,
(
c
,
c
)
}, P
,
S
) be a WK linear grammar, where P consists of the rules (28)
S
⟶
a
λ
S
b
λ
,
S
⟶
a
λ
A
b
λ
,
A
⟶
c
a
A
,
A
⟶
λ
c
B
λ
b
,
B
⟶
λ
c
B
λ
b
,
B
⟶
λ
λ
.In general, we have the derivation (29)
S
⟹
∗
a
n
-
1
λ
S
b
n
-
1
λ
⟹
a
n
λ
A
b
n
λ
⟹
∗
a
n
c
n
a
n
A
b
n
λ
⟹
a
n
c
n
a
n
c
B
b
n
b
⟹
∗
a
n
c
n
a
n
c
n
B
b
n
b
n
⟹
a
n
c
n
b
n
a
n
c
n
b
n
.Thus, G
1 generates the language L
(
G
1
)
=
{
a
n
c
n
b
n
:
n
≥
1
}
∈
C
S
-
C
F.Example 11.
Let(30)
G
2
=
S
,
A
,
B
,
C
,
D
,
a
,
b
,
c
,
d
,
a
,
a
,
b
,
b
,
c
,
c
,
d
,
d
,
P
,
Sbe a WK regular grammar, and P consists of the rules (31)
S
⟶
a
λ
S
∣
a
λ
A
,
A
⟶
b
λ
A
∣
b
λ
B
,
B
⟶
c
a
B
∣
c
a
C
,
C
⟶
d
b
C
∣
d
b
D
,
D
⟶
λ
c
D
∣
λ
d
D
∣
λ
λ
.Then, we have the following derivation for n
,
m
≥
1: (32)
S
⟹
∗
a
n
-
1
λ
S
⟹
a
n
λ
A
⟹
∗
a
n
b
m
-
1
λ
A
⟹
a
n
b
m
λ
B
⟹
∗
a
n
b
m
c
n
-
1
a
n
-
1
B
⟹
a
n
b
m
c
n
a
n
C
⟹
∗
a
n
b
m
c
n
d
m
-
1
a
n
b
m
-
1
C
⟹
a
n
b
m
c
n
d
m
a
n
b
m
D
⟹
∗
a
n
b
m
c
n
d
m
a
n
b
m
c
n
D
⟹
∗
a
n
b
m
c
n
d
m
a
n
b
m
c
n
d
m
D
⟹
a
n
b
m
c
n
d
m
a
n
b
m
c
n
d
m
.Hence, L
(
G
2
)
=
{
a
n
b
m
c
n
d
m
:
n
,
m
≥
1
}
∈
C
S
-
C
F.Example 12.
LetG
3
=
(
{
S
,
A
,
B
,
C
}
,
{
a
,
b
,
c
}
,
{
(
a
,
a
)
,
(
b
,
b
)
}, P
,
S) be a WK linear grammar with P consisting of the following rules: (33)
S
⟶
a
λ
S
∣
b
λ
S
∣
c
λ
A
,
A
⟶
a
a
A
∣
b
b
A
∣
λ
c
B
,
B
⟶
λ
a
B
∣
λ
b
B
∣
λ
λ
.By rules S
→
a
/
λ and S
→
b
/
λ, we obtain a sentential form w
/
λ
S where w
∈
{
a
,
b
}
∗. The derivation is continued by only possible rule S
→
c
/
λ
A and we have w
c
/
λ
A. Further, we can only apply rules A
→
a
/
a
A and A
→
b
/
b
A. By the symmetric relation ρ, the derivation results in w
c
w
/
w
A. Then, we can only apply A
→
λ
/
c
B continuing with rules B
→
λ
/
a
B and B
→
λ
/
b
B and obtain w
c
w
/
w
c
w
B. Finally, by rule B
→
λ
/
λ, we get [
w
c
w
/
w
c
w
]. Illustratively, (34)
S
⟹
∗
w
λ
S
⟹
w
c
λ
A
⟹
∗
w
c
w
w
A
⟹
w
c
w
w
c
B
⟹
∗
w
c
w
w
c
w
B
⟹
w
c
w
w
c
w
.Thus, L
(
G
3
)
=
{
w
c
w
:
w
∈
{
a
,
b
}
∗
}
∈
C
S
-
C
F.The following theorem follows from Lemma9 and Examples 10, 11, and 12.Theorem 13.
The following inclusions hold:(35)
L
I
N
⊊
W
K
L
I
N
,
W
K
R
E
G
-
C
F
≠
∅
,
W
K
L
I
N
-
C
F
≠
∅
.The following example shows that some WK linear languages cannot be generated by WK regular grammars.Lemma 14.
The following language is not a WK regular language:(36)
L
1
=
a
n
b
m
a
n
:
2
n
≤
m
≤
3
n
∈
W
K
L
I
N
-
W
K
R
E
G
.Proof.
The languageL
1 can be generated by the following WK linear grammar G
4
=
(
{
S
,
A
,
B
}
,
{
a
,
b
}
,
{
(
a
,
a
)
,
(
b
,
b
)
}
,
S
,
P
), where P consists of the rules: (37)
S
⟶
a
λ
S
a
a
∣
a
λ
A
a
a
,
A
⟶
b
b
a
A
∣
b
b
b
a
A
∣
λ
b
B
,
B
⟶
λ
b
B
∣
λ
λ
.It is not difficult to see that (38)
S
⟹
∗
a
n
-
1
λ
S
a
n
-
1
a
n
-
1
⟹
a
n
λ
A
a
n
a
n
⟹
∗
a
n
b
m
a
n
A
a
n
a
n
⟹
a
n
b
m
a
n
b
B
a
n
a
n
⟹
∗
a
n
b
m
a
n
b
m
B
a
n
a
n
⟹
a
n
b
m
a
n
a
n
b
m
a
n
,where 2
n
≤
m
≤
3
n.
Next, we show thatL
1
∉
W
K
R
E
G.
We suppose, by contradiction, thatL
1 can be generated by a WK regular grammar G
′
=
(
N
,
{
a
,
b
}
,
ρ
,
S
,
P
). Without loss of generality, we assume that G
′ is in 1-normal form. Then, for each rule u
→
v in P, we have u
∈
N and (39)
v
∈
a
λ
,
λ
a
,
a
a
,
b
λ
,
λ
b
,
b
b
,
a
b
,
b
b
N
∪
λ
.Let w
=
a
r
b
s
a
r be a string in L
1 such that r
>
|
P
|. Then, the double-stranded sequence [
a
r
b
s
a
r
/
a
r
b
s
a
r
] is generated by the grammar G
′.
Case  1. In any derivation for this string, first b can occur in the upper (or lower) strand if a
r has already been generated in the upper (or lower) strand. Thus, we obtain two possible successful derivations: (40)
S
⟹
∗
a
r
b
a
k
or
S
⟹
∗
a
r
b
a
r
b
,where k
≤
r. In the latter derivation in (40), we cannot control the number of occurrences of b; that is, the derivation may not be successful. In the former derivation in (40), using the second strand, we can generate b
s:(41)
S
⟹
∗
a
r
b
a
k
⟹
∗
a
r
b
s
a
r
b
t
,
t
≤
s
.Equation (41) is continued by generating a’s in the first strand and we can use the second strand to control their number. Consider(42)
S
⟹
∗
a
r
b
a
k
⟹
∗
a
r
b
s
a
r
b
t
⟹
∗
a
r
b
s
a
i
a
r
b
s
a
j
,and i is related to s. Since 2
r
≤
s
≤
3
r, generally, i is not the same as r for all derivations.
Case  2. We can control the number of a’s after b’s by using the second strand for a’s before b’s. In this case, the number of b’s cannot be related to the number of a’s: (43)
S
⟹
∗
a
r
b
l
a
r
a
r
.In both cases, we cannot control the number of b’s and the number of a’s after b’s at the same time using WK regular rules.Since stringsa
n
b
m
a
n are palindrome strings for even m’s, the language {
w
w
R
:
w
∈
{
a
,
b
}
∗
} is not in W
K
R
E
G; that is, we have the following.Corollary 15.
The following holds:(44)
L
I
N
-
W
K
R
E
G
≠
∅
.


### 4.3. Hierarchy of the Families of Watson-Crick Languages

Combining the results above, we obtain the following theorem.Theorem 16.
The relations in Figure4 hold; the dotted lines denote incomparability of the language families and the arrows denote proper inclusions of the lower families into the upper families, while the dotted arrows denote inclusions.Figure 4
The hierarchy of WK and Chomsky language families.


## 4.1. A Normal Form for Watson-Crick Linear Grammars

Next, we define1-normal form for WK linear grammars and show that, for every WK linear grammar G, there is an equivalent WK linear grammar G
′ in the normal form; that is, L
(
G
)
=
L
(
G
′
).Definition 7.
A linear WK grammarG
=
(
N
,
T
,
ρ
,
P
,
S
) is said to be in the 1-normal form if each rule in P of the form (21)
A
⟶
u
1
v
1
B
u
2
v
2
or
A
⟶
u
1
v
1
,where |
u
i
|
≤
1, |
v
i
|
≤
1, i
=
1,2, and A
,
B
∈
N.Lemma 8.
For every WK linear grammarG, there exists an equivalent WK linear grammar G
′ in the 1-normal form.Proof.
LetG
=
(
N
,
T
,
ρ
,
S
,
P
) be a WK linear grammar. Let(22)
A
⟶
a
11
⋯
a
1
m
1
b
11
⋯
b
1
n
1
B
a
2
m
2
⋯
a
21
b
2
n
2
⋯
b
21be a production in P where m
1
>
1, m
2
>
1, n
1
>
1, or n
2
>
1. Without loss of generality, we assume that m
1
≥
n
1 and m
2
≥
n
2. Then, we define the following sequence of right-linear and left-linear production rules: (23)
A
⟶
a
11
b
11
A
11
r
,
A
11
r
⟶
a
12
b
12
A
12
r
⋮
A
1
n
1
-
1
r
⟶
a
1
n
1
b
1
n
1
A
1
n
1
r
,
A
1
n
1
r
⟶
a
1
n
1
+
1
λ
A
1
n
1
+
1
r
⋮
A
1
m
1
-
1
r
⟶
a
1
m
1
λ
A
1
m
1
r
,
A
1
m
1
r
⟶
A
21
r
a
21
b
21
,
A
21
r
⟶
A
22
r
a
22
b
22
⋮
A
1
n
2
-
1
r
⟶
A
2
n
2
r
a
2
n
2
b
2
n
2
,
A
2
n
2
r
⟶
A
2
n
2
+
1
r
a
2
n
2
+
1
λ
⋮
A
2
m
2
-
1
r
⟶
a
2
m
2
λ
,where A
1
j
r, 1
≤
j
≤
m
1, and A
2
j
r, 1
≤
j
≤
m
2
-
1, are new nonterminals.
Let(24)
r
:
A
⟶
a
1
a
2
⋯
a
m
b
1
b
2
⋯
b
n
∈
P
,where m
>
1 or n
>
1. Without loss of generality, we assume that m
≥
n. Then, we define the following sequence of right-linear production rules: (25)
A
⟶
a
1
b
1
A
1
r
,
A
1
r
⟶
a
2
b
2
A
2
r
,
A
n
-
1
r
⟶
a
n
b
n
A
n
r
,
A
n
r
⟶
a
n
+
1
λ
A
n
+
1
r
⋮
A
m
-
1
r
⟶
a
m
λ
,where A
i
r, 1
≤
i
≤
m
-
1, are new nonterminals.
We construct a WK linear grammarG
′
=
(
N
∪
N
′
,
T
,
ρ
,
S
,
P
∪
P
′
), where P
′ consists of productions defined above for each A
→
u
1
/
v
1
B
u
2
/
v
2
∈
P with |
u
1
|
>
1, |
v
1
|
>
1, |
u
2
|
>
1, or |
v
2
|
>
1 and A
→
u
/
v
∈
P with |
u
|
>
1 or |
v
|
>
1. Then, it is not difficult to see that, in every derivation, productions in the form of (22) and (24) in G can be replaced by the sequences of productions (23) and (25) in G
′ and vice versa. Thus, L
(
G
)
=
L
(
G
′
).


## 4.2. The Generative Power

The following results immediately follow from the definition of WK grammars.Lemma 9.
The following inclusions hold:(26)
W
K
R
E
G
⊆
W
K
L
I
N
,
L
I
N
⊆
W
K
L
I
N
,
C
F
⊆
W
K
C
F
.Next, we show that WK grammars can generate non-context-free languages:(27)
a
n
c
n
b
n
:
n
≥
1
,
a
n
b
m
c
n
d
m
:
n
,
m
≥
1
,
w
c
w
:
w
∈
a
,
b
∗
.Example 10.
LetG
1
=
(
{
S
,
A
,
B
}
,
{
a
,
b
,
c
}
,
{
(
a
,
a
)
,
(
b
,
b
)
,
(
c
,
c
)
}, P
,
S
) be a WK linear grammar, where P consists of the rules (28)
S
⟶
a
λ
S
b
λ
,
S
⟶
a
λ
A
b
λ
,
A
⟶
c
a
A
,
A
⟶
λ
c
B
λ
b
,
B
⟶
λ
c
B
λ
b
,
B
⟶
λ
λ
.In general, we have the derivation (29)
S
⟹
∗
a
n
-
1
λ
S
b
n
-
1
λ
⟹
a
n
λ
A
b
n
λ
⟹
∗
a
n
c
n
a
n
A
b
n
λ
⟹
a
n
c
n
a
n
c
B
b
n
b
⟹
∗
a
n
c
n
a
n
c
n
B
b
n
b
n
⟹
a
n
c
n
b
n
a
n
c
n
b
n
.Thus, G
1 generates the language L
(
G
1
)
=
{
a
n
c
n
b
n
:
n
≥
1
}
∈
C
S
-
C
F.Example 11.
Let(30)
G
2
=
S
,
A
,
B
,
C
,
D
,
a
,
b
,
c
,
d
,
a
,
a
,
b
,
b
,
c
,
c
,
d
,
d
,
P
,
Sbe a WK regular grammar, and P consists of the rules (31)
S
⟶
a
λ
S
∣
a
λ
A
,
A
⟶
b
λ
A
∣
b
λ
B
,
B
⟶
c
a
B
∣
c
a
C
,
C
⟶
d
b
C
∣
d
b
D
,
D
⟶
λ
c
D
∣
λ
d
D
∣
λ
λ
.Then, we have the following derivation for n
,
m
≥
1: (32)
S
⟹
∗
a
n
-
1
λ
S
⟹
a
n
λ
A
⟹
∗
a
n
b
m
-
1
λ
A
⟹
a
n
b
m
λ
B
⟹
∗
a
n
b
m
c
n
-
1
a
n
-
1
B
⟹
a
n
b
m
c
n
a
n
C
⟹
∗
a
n
b
m
c
n
d
m
-
1
a
n
b
m
-
1
C
⟹
a
n
b
m
c
n
d
m
a
n
b
m
D
⟹
∗
a
n
b
m
c
n
d
m
a
n
b
m
c
n
D
⟹
∗
a
n
b
m
c
n
d
m
a
n
b
m
c
n
d
m
D
⟹
a
n
b
m
c
n
d
m
a
n
b
m
c
n
d
m
.Hence, L
(
G
2
)
=
{
a
n
b
m
c
n
d
m
:
n
,
m
≥
1
}
∈
C
S
-
C
F.Example 12.
LetG
3
=
(
{
S
,
A
,
B
,
C
}
,
{
a
,
b
,
c
}
,
{
(
a
,
a
)
,
(
b
,
b
)
}, P
,
S) be a WK linear grammar with P consisting of the following rules: (33)
S
⟶
a
λ
S
∣
b
λ
S
∣
c
λ
A
,
A
⟶
a
a
A
∣
b
b
A
∣
λ
c
B
,
B
⟶
λ
a
B
∣
λ
b
B
∣
λ
λ
.By rules S
→
a
/
λ and S
→
b
/
λ, we obtain a sentential form w
/
λ
S where w
∈
{
a
,
b
}
∗. The derivation is continued by only possible rule S
→
c
/
λ
A and we have w
c
/
λ
A. Further, we can only apply rules A
→
a
/
a
A and A
→
b
/
b
A. By the symmetric relation ρ, the derivation results in w
c
w
/
w
A. Then, we can only apply A
→
λ
/
c
B continuing with rules B
→
λ
/
a
B and B
→
λ
/
b
B and obtain w
c
w
/
w
c
w
B. Finally, by rule B
→
λ
/
λ, we get [
w
c
w
/
w
c
w
]. Illustratively, (34)
S
⟹
∗
w
λ
S
⟹
w
c
λ
A
⟹
∗
w
c
w
w
A
⟹
w
c
w
w
c
B
⟹
∗
w
c
w
w
c
w
B
⟹
w
c
w
w
c
w
.Thus, L
(
G
3
)
=
{
w
c
w
:
w
∈
{
a
,
b
}
∗
}
∈
C
S
-
C
F.The following theorem follows from Lemma9 and Examples 10, 11, and 12.Theorem 13.
The following inclusions hold:(35)
L
I
N
⊊
W
K
L
I
N
,
W
K
R
E
G
-
C
F
≠
∅
,
W
K
L
I
N
-
C
F
≠
∅
.The following example shows that some WK linear languages cannot be generated by WK regular grammars.Lemma 14.
The following language is not a WK regular language:(36)
L
1
=
a
n
b
m
a
n
:
2
n
≤
m
≤
3
n
∈
W
K
L
I
N
-
W
K
R
E
G
.Proof.
The languageL
1 can be generated by the following WK linear grammar G
4
=
(
{
S
,
A
,
B
}
,
{
a
,
b
}
,
{
(
a
,
a
)
,
(
b
,
b
)
}
,
S
,
P
), where P consists of the rules: (37)
S
⟶
a
λ
S
a
a
∣
a
λ
A
a
a
,
A
⟶
b
b
a
A
∣
b
b
b
a
A
∣
λ
b
B
,
B
⟶
λ
b
B
∣
λ
λ
.It is not difficult to see that (38)
S
⟹
∗
a
n
-
1
λ
S
a
n
-
1
a
n
-
1
⟹
a
n
λ
A
a
n
a
n
⟹
∗
a
n
b
m
a
n
A
a
n
a
n
⟹
a
n
b
m
a
n
b
B
a
n
a
n
⟹
∗
a
n
b
m
a
n
b
m
B
a
n
a
n
⟹
a
n
b
m
a
n
a
n
b
m
a
n
,where 2
n
≤
m
≤
3
n.
Next, we show thatL
1
∉
W
K
R
E
G.
We suppose, by contradiction, thatL
1 can be generated by a WK regular grammar G
′
=
(
N
,
{
a
,
b
}
,
ρ
,
S
,
P
). Without loss of generality, we assume that G
′ is in 1-normal form. Then, for each rule u
→
v in P, we have u
∈
N and (39)
v
∈
a
λ
,
λ
a
,
a
a
,
b
λ
,
λ
b
,
b
b
,
a
b
,
b
b
N
∪
λ
.Let w
=
a
r
b
s
a
r be a string in L
1 such that r
>
|
P
|. Then, the double-stranded sequence [
a
r
b
s
a
r
/
a
r
b
s
a
r
] is generated by the grammar G
′.
Case  1. In any derivation for this string, first b can occur in the upper (or lower) strand if a
r has already been generated in the upper (or lower) strand. Thus, we obtain two possible successful derivations: (40)
S
⟹
∗
a
r
b
a
k
or
S
⟹
∗
a
r
b
a
r
b
,where k
≤
r. In the latter derivation in (40), we cannot control the number of occurrences of b; that is, the derivation may not be successful. In the former derivation in (40), using the second strand, we can generate b
s:(41)
S
⟹
∗
a
r
b
a
k
⟹
∗
a
r
b
s
a
r
b
t
,
t
≤
s
.Equation (41) is continued by generating a’s in the first strand and we can use the second strand to control their number. Consider(42)
S
⟹
∗
a
r
b
a
k
⟹
∗
a
r
b
s
a
r
b
t
⟹
∗
a
r
b
s
a
i
a
r
b
s
a
j
,and i is related to s. Since 2
r
≤
s
≤
3
r, generally, i is not the same as r for all derivations.
Case  2. We can control the number of a’s after b’s by using the second strand for a’s before b’s. In this case, the number of b’s cannot be related to the number of a’s: (43)
S
⟹
∗
a
r
b
l
a
r
a
r
.In both cases, we cannot control the number of b’s and the number of a’s after b’s at the same time using WK regular rules.Since stringsa
n
b
m
a
n are palindrome strings for even m’s, the language {
w
w
R
:
w
∈
{
a
,
b
}
∗
} is not in W
K
R
E
G; that is, we have the following.Corollary 15.
The following holds:(44)
L
I
N
-
W
K
R
E
G
≠
∅
.


## 4.3. Hierarchy of the Families of Watson-Crick Languages

Combining the results above, we obtain the following theorem.Theorem 16.
The relations in Figure4 hold; the dotted lines denote incomparability of the language families and the arrows denote proper inclusions of the lower families into the upper families, while the dotted arrows denote inclusions.Figure 4
The hierarchy of WK and Chomsky language families.


## 5. Closure Properties

In this section, we establish results regarding the closure properties of WK grammars. The families of WK languages are shown to be higher in the hierarchy than their respective Chomsky language families; thus it is interesting to see how WK grammars work in terms of closure properties as the ones for the Chomsky languages. Moreover, researching closure properties of WK grammars ensure the safety and correctness of the results yielded when performing operations on the sets of DNA molecules generated by some WK grammars.


### 5.1. Watson-Crick Regular Grammars

LetL
1
,
L
2
∈
W
K
R
E
G, and G
1
=
(
N
1
,
T
,
S
1
,
P
1
,
ρ
), G
2
=
(
N
2
,
T
,
S
2
,
P
2
,
ρ
) be Watson-Crick regular grammars generating languages L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∩
N
2
≠
∅ and S
1 and S
2 do not appear on the right-hand side of any production rule.Lemma 17 (union).
W
K
R
E
G is closed under union.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
) by setting N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∪
N
2, and (45)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then it is not difficult to see that L
(
G
)
=
L
1
∪
L
2.Lemma 18 (concatenation).
W
K
R
E
G is closed under concatenation.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2 and S
=
S
1. We define (46)
P
=
P
2
∪
P
1
-
A
⟶
u
v
∈
P
1
∪
A
⟶
u
v
S
2
∣
A
⟶
u
v
∈
P
1
.Then it is obvious that L
(
G
)
=
L
1
·
L
2.Lemma 19 (Kleene-star).
W
K
R
E
G is closed under Kleene-star operation.Proof.
Define the WK regular grammarG
=
(
N
1
,
T
1
,
S
,
P
1
,
ρ
) with (47)
P
1
=
P
1
-
P
T
∪
P
S
∪
S
1
⟶
λ
,where (48)
P
T
=
A
⟶
u
v
∈
P
:
u
v
∈
T
∗
T
∗
,
P
S
=
A
⟶
u
v
S
1
∣
A
⟶
u
v
∈
P
T
.Then, L
(
G
)
=
L
1
∗.Lemma 20 (finite substitution and homomorphism).
W
K
R
E
G is closed under finite substitution and homomorphism.Proof.
We show that the finite substitution (homomorphism) ofL
1 is also in W
K
R
E
G. Let s
:
T
∗
→
Σ
∗ be a finite substitution (homomorphism). Define G
=
(
N
1
,
T
1
,
S
1
,
P
,
ρ
1
), where L
(
G
)
=
s
(
L
1
). Without loss of generality, we assume that G
1 is in the 1-normal form. Then, P
1 can contain production rules of the forms (49)
A
⟶
a
b
B
,
A
⟶
a
b
,
A
⟶
a
λ
B
,
A
⟶
a
λ
,
A
⟶
λ
b
B
,
A
⟶
λ
b
,
A
⟶
λ
λ
.
We defineP as the set of production rules of the forms (50)
A
⟶
s
a
s
b
B
,
A
⟶
s
a
s
b
,
A
⟶
s
a
λ
B
,
A
⟶
s
a
λ
,
A
⟶
λ
s
b
B
,
A
⟶
λ
s
b
,
A
⟶
λ
λ
.
Since the substitution/homomorphisms is finite, P is a finite set too; that is, G is a WK regular grammar, and L
(
G
)
=
s
(
L
1
).Lemma 21 (mirror image).
W
K
R
E
G is closed under mirror image.Proof.
We show thatL
1
R
∈
W
K
R
E
G. Define G
=
(
N
1
∪
{
S
}
,
T
1
,
S
,
P
,
ρ
1
) generating the language L
1
R, where S is a new nonterminal and P consists of production rules defined as follows: (i)
A
→
B
u
/
v, where A
→
u
/
v
B
∈
P
1,
(ii)
A
→
u
/
v, where A
→
u
/
v
∈
P
1.The results obtained from the lemmas above are summarized in the following theorem.Theorem 22.
The family of Watson-Crick regular languages is closed under union, concatenation, Kleene-star, finite substitution, homomorphism, and mirror image.This shows that WK regular grammars preserve almost all of the closure properties of regular grammars. Other closure properties of WK regular grammars are left for future studies.


### 5.2. Watson-Crick Linear Grammars

Similar to the subsection above, a Watson-Crick linear grammarG is constructed for the purpose of investigating the closure properties of W
K
L
I
N.LetL
1
,
L
2
∈
W
K
L
I
N, and (51)
G
1
=
N
1
,
T
,
S
1
,
P
1
,
ρ
,
G
2
=
N
2
,
T
,
S
2
,
P
2
,
ρbe Watson-Crick linear grammars generating L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∪
N
2
≠
∅.Lemma 23 (union).
W
K
L
I
N is closed under union.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∪
N
2 and (52)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then, L
(
G
)
=
L
1
∪
L
2.Lemma 24 (homomorphism).
W
K
L
I
N is closed under homomorphism.Proof.
DefineG
=
(
N
1
,
T
,
S
1
,
P
,
ρ
), where L
(
G
)
=
h
(
L
1
). We show that the homomorphism of L
1 is also in W
K
L
I
N. Let h
:
T
∗
→
Σ
∗ be a homomorphism. Without loss of generality, we assume that G
1 is in the 1-normal form. For each rule (53)
r
:
A
⟶
u
1
v
1
B
u
2
v
2
∈
P
1
,where u
1
,
v
1
,
u
2
,
v
2
∈
T
∪
{
λ
}, we construct (54)
h
r
:
A
⟶
h
u
1
h
v
1
B
h
u
2
h
v
2in P.
In every successful derivation ofG
1 generating [
w
/
w
]
∈
[
T
/
T
]
∗, we replace production rule r
∈
P
1 with the production rule h
(
r
)
∈
P and obtain the string [
h
(
w
)
/
h
(
w
)
]
∈
[
Σ
/
Σ
]
∗. Thus, h
(
w
)
∈
h
(
L
1
).Theorem 25.
The family of Watson-Crick linear languages is closed under union and homomorphism.It is compelling to prove if the concatenation of two WK linear grammars is still included inW
K
L
I
N or not. This also decides whether WK linear grammars are unique from linear grammars or not, as linear grammars are not closed under concatenation and thus not closed under Kleene-star operation.


### 5.3. Watson-Crick Context-Free Grammars

LetL
1
,
L
2
,
L
∈
W
K
C
F, and G
1
=
(
N
1
,
T
,
S
1
,
P
1
,
ρ
)
,
G
2
=
(
N
2
,
T
,
S
2
,
P
2
,
ρ
) be Watson-Crick context-free grammars generating L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∪
N
2
≠
∅.Lemma 26 (union).
W
K
C
F is closed under union operation.Proof.
Define the WK context-free grammarG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∩
N
2, and (55)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then it is obvious that L
(
G
)
=
L
1
∪
L
2.Lemma 27 (concatenation).
W
K
C
F is closed under concatenation.Proof.
DefineG
=
(
N
1
∪
N
2
∪
{
S
}
,
T
1
∪
T
2
,
S
,
P
,
ρ
) where S
∉
(
N
1
∪
N
2
), and (56)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
S
2
.Then, L
(
G
)
∈
W
K
C
F.Lemma 28 (Kleene-star).
W
K
C
F is closed under Kleene-star operation.Proof.
DefineG
=
(
N
1
∪
{
S
}
,
T
1
,
S
,
P
,
ρ
)
∈
W
K
C
F setting (57)
P
=
P
1
∪
S
⟶
S
1
S
∣
λ
.Then it is not difficult to see that L
(
G
)
∈
W
K
C
F.Lemma 29 (homomorphism).
W
K
C
F is closed under homomorphism.Proof.
DefineG
=
(
N
1
,
T
,
S
1
,
P
,
ρ
), where L
(
G
)
=
h
(
L
1
). We show that the homomorphism of L
1 is also in W
K
C
F. Let s
:
T
∗
→
Σ
∗ be a homomorphism. P
1 contains production rules of the form (58)
r
:
A
⟶
u
1
v
1
B
1
u
2
v
2
B
2
⋯
u
k
v
k
B
k
u
k
+
1
v
k
+
1
,where k
≥
0
.
For each ruler
∈
P, we construct(59)
h
r
:
A
⟶
h
u
1
h
v
1
B
1
h
u
2
h
v
2
B
2
⋯
h
u
k
h
v
k
B
k
h
u
k
+
1
h
v
k
+
1
,where k
≥
0.
In every successful derivation ofG
1 generating [
w
/
w
]
∈
[
T
/
T
]
∗, we replace production rule r
∈
P
1 with the production rule h
(
r
)
∈
P and obtain the string [
h
(
w
)
/
h
(
w
)
]
∈
[
Σ
/
Σ
]
∗. Thus, h
(
w
)
∈
h
(
L
1
).With the lemmas provided above in this subsection, the next theorem follows.Theorem 30.
The family of Watson-Crick context-free languages is closed under union, concatenation, Kleene-star, and homomorphism.Closure ofW
K
C
F under complement and intersection depends on the generative capacity of W
K
C
F. The nonclosure of context-free (CF) grammars for intersection was shown with the famous example that the intersection of two CF languages results in a string that cannot be generated by a CF grammars. If one can provide some examples of strings that cannot be generated by WK context-free grammars, then the nonclosure of W
K
C
F can be proven.


## 5.1. Watson-Crick Regular Grammars

LetL
1
,
L
2
∈
W
K
R
E
G, and G
1
=
(
N
1
,
T
,
S
1
,
P
1
,
ρ
), G
2
=
(
N
2
,
T
,
S
2
,
P
2
,
ρ
) be Watson-Crick regular grammars generating languages L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∩
N
2
≠
∅ and S
1 and S
2 do not appear on the right-hand side of any production rule.Lemma 17 (union).
W
K
R
E
G is closed under union.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
) by setting N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∪
N
2, and (45)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then it is not difficult to see that L
(
G
)
=
L
1
∪
L
2.Lemma 18 (concatenation).
W
K
R
E
G is closed under concatenation.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2 and S
=
S
1. We define (46)
P
=
P
2
∪
P
1
-
A
⟶
u
v
∈
P
1
∪
A
⟶
u
v
S
2
∣
A
⟶
u
v
∈
P
1
.Then it is obvious that L
(
G
)
=
L
1
·
L
2.Lemma 19 (Kleene-star).
W
K
R
E
G is closed under Kleene-star operation.Proof.
Define the WK regular grammarG
=
(
N
1
,
T
1
,
S
,
P
1
,
ρ
) with (47)
P
1
=
P
1
-
P
T
∪
P
S
∪
S
1
⟶
λ
,where (48)
P
T
=
A
⟶
u
v
∈
P
:
u
v
∈
T
∗
T
∗
,
P
S
=
A
⟶
u
v
S
1
∣
A
⟶
u
v
∈
P
T
.Then, L
(
G
)
=
L
1
∗.Lemma 20 (finite substitution and homomorphism).
W
K
R
E
G is closed under finite substitution and homomorphism.Proof.
We show that the finite substitution (homomorphism) ofL
1 is also in W
K
R
E
G. Let s
:
T
∗
→
Σ
∗ be a finite substitution (homomorphism). Define G
=
(
N
1
,
T
1
,
S
1
,
P
,
ρ
1
), where L
(
G
)
=
s
(
L
1
). Without loss of generality, we assume that G
1 is in the 1-normal form. Then, P
1 can contain production rules of the forms (49)
A
⟶
a
b
B
,
A
⟶
a
b
,
A
⟶
a
λ
B
,
A
⟶
a
λ
,
A
⟶
λ
b
B
,
A
⟶
λ
b
,
A
⟶
λ
λ
.
We defineP as the set of production rules of the forms (50)
A
⟶
s
a
s
b
B
,
A
⟶
s
a
s
b
,
A
⟶
s
a
λ
B
,
A
⟶
s
a
λ
,
A
⟶
λ
s
b
B
,
A
⟶
λ
s
b
,
A
⟶
λ
λ
.
Since the substitution/homomorphisms is finite, P is a finite set too; that is, G is a WK regular grammar, and L
(
G
)
=
s
(
L
1
).Lemma 21 (mirror image).
W
K
R
E
G is closed under mirror image.Proof.
We show thatL
1
R
∈
W
K
R
E
G. Define G
=
(
N
1
∪
{
S
}
,
T
1
,
S
,
P
,
ρ
1
) generating the language L
1
R, where S is a new nonterminal and P consists of production rules defined as follows: (i)
A
→
B
u
/
v, where A
→
u
/
v
B
∈
P
1,
(ii)
A
→
u
/
v, where A
→
u
/
v
∈
P
1.The results obtained from the lemmas above are summarized in the following theorem.Theorem 22.
The family of Watson-Crick regular languages is closed under union, concatenation, Kleene-star, finite substitution, homomorphism, and mirror image.This shows that WK regular grammars preserve almost all of the closure properties of regular grammars. Other closure properties of WK regular grammars are left for future studies.


## 5.2. Watson-Crick Linear Grammars

Similar to the subsection above, a Watson-Crick linear grammarG is constructed for the purpose of investigating the closure properties of W
K
L
I
N.LetL
1
,
L
2
∈
W
K
L
I
N, and (51)
G
1
=
N
1
,
T
,
S
1
,
P
1
,
ρ
,
G
2
=
N
2
,
T
,
S
2
,
P
2
,
ρbe Watson-Crick linear grammars generating L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∪
N
2
≠
∅.Lemma 23 (union).
W
K
L
I
N is closed under union.Proof.
DefineG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∪
N
2 and (52)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then, L
(
G
)
=
L
1
∪
L
2.Lemma 24 (homomorphism).
W
K
L
I
N is closed under homomorphism.Proof.
DefineG
=
(
N
1
,
T
,
S
1
,
P
,
ρ
), where L
(
G
)
=
h
(
L
1
). We show that the homomorphism of L
1 is also in W
K
L
I
N. Let h
:
T
∗
→
Σ
∗ be a homomorphism. Without loss of generality, we assume that G
1 is in the 1-normal form. For each rule (53)
r
:
A
⟶
u
1
v
1
B
u
2
v
2
∈
P
1
,where u
1
,
v
1
,
u
2
,
v
2
∈
T
∪
{
λ
}, we construct (54)
h
r
:
A
⟶
h
u
1
h
v
1
B
h
u
2
h
v
2in P.
In every successful derivation ofG
1 generating [
w
/
w
]
∈
[
T
/
T
]
∗, we replace production rule r
∈
P
1 with the production rule h
(
r
)
∈
P and obtain the string [
h
(
w
)
/
h
(
w
)
]
∈
[
Σ
/
Σ
]
∗. Thus, h
(
w
)
∈
h
(
L
1
).Theorem 25.
The family of Watson-Crick linear languages is closed under union and homomorphism.It is compelling to prove if the concatenation of two WK linear grammars is still included inW
K
L
I
N or not. This also decides whether WK linear grammars are unique from linear grammars or not, as linear grammars are not closed under concatenation and thus not closed under Kleene-star operation.


## 5.3. Watson-Crick Context-Free Grammars

LetL
1
,
L
2
,
L
∈
W
K
C
F, and G
1
=
(
N
1
,
T
,
S
1
,
P
1
,
ρ
)
,
G
2
=
(
N
2
,
T
,
S
2
,
P
2
,
ρ
) be Watson-Crick context-free grammars generating L
1 and L
2, respectively; that is, L
1
=
L
(
G
1
) and L
2
=
L
(
G
2
). Without loss of generality, we can assume that N
1
∪
N
2
≠
∅.Lemma 26 (union).
W
K
C
F is closed under union operation.Proof.
Define the WK context-free grammarG
=
(
N
,
T
,
S
,
P
,
ρ
), where N
=
N
1
∪
N
2
∪
{
S
} with S
∉
N
1
∩
N
2, and (55)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
∪
S
⟶
S
2
.Then it is obvious that L
(
G
)
=
L
1
∪
L
2.Lemma 27 (concatenation).
W
K
C
F is closed under concatenation.Proof.
DefineG
=
(
N
1
∪
N
2
∪
{
S
}
,
T
1
∪
T
2
,
S
,
P
,
ρ
) where S
∉
(
N
1
∪
N
2
), and (56)
P
=
P
1
∪
P
2
∪
S
⟶
S
1
S
2
.Then, L
(
G
)
∈
W
K
C
F.Lemma 28 (Kleene-star).
W
K
C
F is closed under Kleene-star operation.Proof.
DefineG
=
(
N
1
∪
{
S
}
,
T
1
,
S
,
P
,
ρ
)
∈
W
K
C
F setting (57)
P
=
P
1
∪
S
⟶
S
1
S
∣
λ
.Then it is not difficult to see that L
(
G
)
∈
W
K
C
F.Lemma 29 (homomorphism).
W
K
C
F is closed under homomorphism.Proof.
DefineG
=
(
N
1
,
T
,
S
1
,
P
,
ρ
), where L
(
G
)
=
h
(
L
1
). We show that the homomorphism of L
1 is also in W
K
C
F. Let s
:
T
∗
→
Σ
∗ be a homomorphism. P
1 contains production rules of the form (58)
r
:
A
⟶
u
1
v
1
B
1
u
2
v
2
B
2
⋯
u
k
v
k
B
k
u
k
+
1
v
k
+
1
,where k
≥
0
.
For each ruler
∈
P, we construct(59)
h
r
:
A
⟶
h
u
1
h
v
1
B
1
h
u
2
h
v
2
B
2
⋯
h
u
k
h
v
k
B
k
h
u
k
+
1
h
v
k
+
1
,where k
≥
0.
In every successful derivation ofG
1 generating [
w
/
w
]
∈
[
T
/
T
]
∗, we replace production rule r
∈
P
1 with the production rule h
(
r
)
∈
P and obtain the string [
h
(
w
)
/
h
(
w
)
]
∈
[
Σ
/
Σ
]
∗. Thus, h
(
w
)
∈
h
(
L
1
).With the lemmas provided above in this subsection, the next theorem follows.Theorem 30.
The family of Watson-Crick context-free languages is closed under union, concatenation, Kleene-star, and homomorphism.Closure ofW
K
C
F under complement and intersection depends on the generative capacity of W
K
C
F. The nonclosure of context-free (CF) grammars for intersection was shown with the famous example that the intersection of two CF languages results in a string that cannot be generated by a CF grammars. If one can provide some examples of strings that cannot be generated by WK context-free grammars, then the nonclosure of W
K
C
F can be proven.


## 6. Applications of Watson-Crick Grammars

In this section, we consider two examples of the applications of Watson-Crick grammars in the analyses of DNA structures and programming language structures.


### 6.1. DNA Structure Analysis

Since Watson-Crick grammars are developed based on the structure and recombinant behavior of DNA molecules, they can suitably be implemented in the study of DNA related problems.The analysis of DNA strings provides useful information: for instance, the finding of a specific pattern in a DNA string and the identification of the repeats of a pattern are very important for detecting mutation. One of the diseases caused by mutation is Huntington disease, resulting from trinucleotide repeat disorders [13–15]. It is discovered that the number of repeats of the trinucleotide C
T
G
/
C
A
G in the patient’s DNA with Huntington disease is not normal. The repeats are also useful for finding the origin of replication of microorganisms [16].In this section, we show that Watson-Crick grammars can be used for analyzing the repeats in DNA strings. We use the DNA of a breed of pig, Sus scrofa breed mixed chromosome 1, Sscrofa10.2 provided by the The National Center for Biotechnology Information (NCBI) database (NCBI Reference Sequence:NC_010443.4) [17].Consider a part of the upper strand of the DNA from the breed stated above with the length of 100 nucleotides:(60)
a
a
t
c
g
a
c
g
c
c
a
c
a
c
g
c
a
g
g
c
c
a
g
t
t
c
c
g
a
g
c
t
g
c
a
t
c
t
g
g
g
a
c
c
t
g
c
t
c
c
a
t
a
t
c
t
g
a
a
g
g
c
a
a
t
c
c
t
g
g
a
t
c
c
a
g
g
g
a
t
t
g
c
a
c
c
t
g
c
c
t
t
c
t
c
t
c
c
t
a
.In this example, the patternc
t
g is being repeated for six times in the direct strand (upper strand) and two times in the reverse strand (lower strand) which can be seen as c
a
g in the upper strand. Focusing on the repeats of c
t
g pattern, a DNA string containing such a pattern can be expressed as (61)
a
,
t
,
c
,
g
∗
c
t
g
a
,
t
,
c
,
g
∗
∗
.We now construct a simple Watson-Crick regular grammarG to generate the above language.LetG
=
(
N
,
T
,
S
,
P
,
ρ
), where T
=
{
a
,
t
,
c
,
g
}, ρ
=
{
(
a
,
t
)
,
(
c
,
g
)
}, and P consists of the following productions:(62)
S
⟶
a
t
S
∣
t
a
S
∣
g
c
S
∣
c
g
A
,
A
⟶
c
g
A
∣
a
t
S
∣
g
c
S
∣
t
a
B
,
B
⟶
c
g
A
∣
a
t
S
∣
t
a
S
∣
g
c
C
,
C
⟶
a
t
C
∣
t
a
C
∣
g
c
C
∣
c
g
A
∣
λ
λ
.For instance, a derivation resulting in six repeats ofc
t
g pattern can be obtained as follows:(63)
S
⟹
∗
x
y
S
⟹
x
c
y
g
A
⟹
x
c
t
y
g
a
B
⟹
x
c
t
g
y
g
a
c
C
⟹
∗
x
c
t
g
x
y
g
a
c
y
A
⟹
x
c
t
g
x
c
y
g
a
c
y
g
A
⟹
x
c
t
g
x
c
t
y
g
a
c
y
g
a
B
⟹
x
c
t
g
x
c
t
g
y
g
a
c
y
g
a
c
C
⟹
∗
x
c
t
g
x
c
t
g
x
y
g
a
c
y
g
a
c
y
C
⟹
∗
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
,where x
∈
{
a
,
t
,
g
}
∗ and y is their complementarity symbols based on ρ, respectively.Though, in this example, the functionality of WK regular grammars is not used to the fullest, the DNA structures can be naturally and effectively analyzed with WK grammars.


### 6.2. Programming Language Structure Analysis

The ability to differentiate between parentheses that are correctly balanced and those that are unbalanced is an important part of recognizing many programming language structures. Balanced parentheses mean that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.The parsing algorithms of compilers and interpreters have to check the correctness of balanced parentheses in the blocks of codes including algebraic and arithmetic expressions.Although context-free grammars are used to develop parsers for programming languages, many programming language structures are context-sensitive. Thus, it is of interest to develop parsers based on grammars which are able to analyze non-context-free language structures.Further, we show an example of balanced parentheses that can be generated by WK regular grammars but cannot be generated by context-free grammars. One can see that just by incorporating the concept of double-stranded string bonded with Watson-Crick complementarity, even WK grammars that are based of just regular rules can enhance the power of the parsing techniques.To avoid confusion, we denote “(” as the open parenthesis terminal symbol and “)” as the close parenthesis terminal symbol in bold font.Example 31.
LetG
5
=
(
{
S
,
A
,
B
}
,
{
(
,
)
}
,
{
(
(
,
)
)
}
,
S
,
P
5
) be a WK regular grammar. P
5 consists of the rules (64)
S
⟶
(
λ
S
S
⟶
(
λ
A
,
A
⟶
)
(
A
A
⟶
)
(
B
B
⟶
(
)
B
B
⟶
λ
)
B
B
⟶
λ
λ
B
⟶
A
.
From this, we obtain the derivation(65)
S
⟹
(
λ
S
⟹
∗
(
n
λ
A
⟹
(
)
n
(
A
⟹
∗
(
)
n
n
(
n
B
⟹
(
)
n
n
(
)
n
B
⟹
∗
(
)
n
n
(
)
n
n
B
⟹
(
)
n
n
(
(
)
n
n
B
⟹
∗
(
)
n
n
(
n
(
)
n
n
A
⟹
(
)
n
n
(
)
n
(
)
n
n
A
⟹
∗
(
)
n
n
(
)
n
n
(
)
n
n
B
⟹
∗
⋯
⟹
∗
(
)
n
n
k
(
)
n
n
k
,where k
≥
1. Hence, the language obtained is (66)
L
5
=
(
)
n
n
k
:
n
,
k
≥
1
∈
W
K
R
E
G
-
C
F
.


## 6.1. DNA Structure Analysis

Since Watson-Crick grammars are developed based on the structure and recombinant behavior of DNA molecules, they can suitably be implemented in the study of DNA related problems.The analysis of DNA strings provides useful information: for instance, the finding of a specific pattern in a DNA string and the identification of the repeats of a pattern are very important for detecting mutation. One of the diseases caused by mutation is Huntington disease, resulting from trinucleotide repeat disorders [13–15]. It is discovered that the number of repeats of the trinucleotide C
T
G
/
C
A
G in the patient’s DNA with Huntington disease is not normal. The repeats are also useful for finding the origin of replication of microorganisms [16].In this section, we show that Watson-Crick grammars can be used for analyzing the repeats in DNA strings. We use the DNA of a breed of pig, Sus scrofa breed mixed chromosome 1, Sscrofa10.2 provided by the The National Center for Biotechnology Information (NCBI) database (NCBI Reference Sequence:NC_010443.4) [17].Consider a part of the upper strand of the DNA from the breed stated above with the length of 100 nucleotides:(60)
a
a
t
c
g
a
c
g
c
c
a
c
a
c
g
c
a
g
g
c
c
a
g
t
t
c
c
g
a
g
c
t
g
c
a
t
c
t
g
g
g
a
c
c
t
g
c
t
c
c
a
t
a
t
c
t
g
a
a
g
g
c
a
a
t
c
c
t
g
g
a
t
c
c
a
g
g
g
a
t
t
g
c
a
c
c
t
g
c
c
t
t
c
t
c
t
c
c
t
a
.In this example, the patternc
t
g is being repeated for six times in the direct strand (upper strand) and two times in the reverse strand (lower strand) which can be seen as c
a
g in the upper strand. Focusing on the repeats of c
t
g pattern, a DNA string containing such a pattern can be expressed as (61)
a
,
t
,
c
,
g
∗
c
t
g
a
,
t
,
c
,
g
∗
∗
.We now construct a simple Watson-Crick regular grammarG to generate the above language.LetG
=
(
N
,
T
,
S
,
P
,
ρ
), where T
=
{
a
,
t
,
c
,
g
}, ρ
=
{
(
a
,
t
)
,
(
c
,
g
)
}, and P consists of the following productions:(62)
S
⟶
a
t
S
∣
t
a
S
∣
g
c
S
∣
c
g
A
,
A
⟶
c
g
A
∣
a
t
S
∣
g
c
S
∣
t
a
B
,
B
⟶
c
g
A
∣
a
t
S
∣
t
a
S
∣
g
c
C
,
C
⟶
a
t
C
∣
t
a
C
∣
g
c
C
∣
c
g
A
∣
λ
λ
.For instance, a derivation resulting in six repeats ofc
t
g pattern can be obtained as follows:(63)
S
⟹
∗
x
y
S
⟹
x
c
y
g
A
⟹
x
c
t
y
g
a
B
⟹
x
c
t
g
y
g
a
c
C
⟹
∗
x
c
t
g
x
y
g
a
c
y
A
⟹
x
c
t
g
x
c
y
g
a
c
y
g
A
⟹
x
c
t
g
x
c
t
y
g
a
c
y
g
a
B
⟹
x
c
t
g
x
c
t
g
y
g
a
c
y
g
a
c
C
⟹
∗
x
c
t
g
x
c
t
g
x
y
g
a
c
y
g
a
c
y
C
⟹
∗
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
c
t
g
x
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
g
a
c
y
,where x
∈
{
a
,
t
,
g
}
∗ and y is their complementarity symbols based on ρ, respectively.Though, in this example, the functionality of WK regular grammars is not used to the fullest, the DNA structures can be naturally and effectively analyzed with WK grammars.


## 6.2. Programming Language Structure Analysis

The ability to differentiate between parentheses that are correctly balanced and those that are unbalanced is an important part of recognizing many programming language structures. Balanced parentheses mean that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.The parsing algorithms of compilers and interpreters have to check the correctness of balanced parentheses in the blocks of codes including algebraic and arithmetic expressions.Although context-free grammars are used to develop parsers for programming languages, many programming language structures are context-sensitive. Thus, it is of interest to develop parsers based on grammars which are able to analyze non-context-free language structures.Further, we show an example of balanced parentheses that can be generated by WK regular grammars but cannot be generated by context-free grammars. One can see that just by incorporating the concept of double-stranded string bonded with Watson-Crick complementarity, even WK grammars that are based of just regular rules can enhance the power of the parsing techniques.To avoid confusion, we denote “(” as the open parenthesis terminal symbol and “)” as the close parenthesis terminal symbol in bold font.Example 31.
LetG
5
=
(
{
S
,
A
,
B
}
,
{
(
,
)
}
,
{
(
(
,
)
)
}
,
S
,
P
5
) be a WK regular grammar. P
5 consists of the rules (64)
S
⟶
(
λ
S
S
⟶
(
λ
A
,
A
⟶
)
(
A
A
⟶
)
(
B
B
⟶
(
)
B
B
⟶
λ
)
B
B
⟶
λ
λ
B
⟶
A
.
From this, we obtain the derivation(65)
S
⟹
(
λ
S
⟹
∗
(
n
λ
A
⟹
(
)
n
(
A
⟹
∗
(
)
n
n
(
n
B
⟹
(
)
n
n
(
)
n
B
⟹
∗
(
)
n
n
(
)
n
n
B
⟹
(
)
n
n
(
(
)
n
n
B
⟹
∗
(
)
n
n
(
n
(
)
n
n
A
⟹
(
)
n
n
(
)
n
(
)
n
n
A
⟹
∗
(
)
n
n
(
)
n
n
(
)
n
n
B
⟹
∗
⋯
⟹
∗
(
)
n
n
k
(
)
n
n
k
,where k
≥
1. Hence, the language obtained is (66)
L
5
=
(
)
n
n
k
:
n
,
k
≥
1
∈
W
K
R
E
G
-
C
F
.


## 7. Conclusion

In this paper, we defined Watson-Crick regular grammars, Watson-Crick linear grammars, and Watson-Crick context-free grammars. Further, we investigated their computational power and closure properties. We showed that(1)
WK linear grammars can generate some context-sensitive languages;
(2)
the families of linear languages and WK regular languages are strictly included in the family of WK linear grammars;
(3)
the families of WK regular languages and linear languages are not comparable;
(4)
the family of WK linear languages is not comparable with the family of context-free languages;
(5)
WK regular grammars preserves the closure properties similar to the ones of regular languages.The following problems related to the topic remain open:(1)
Are the family of context-free languages proper subset of the family of WK linear languages or are they not comparable?
(2)
What is the generative capacity of Watson-Crick context-free grammars?
(3)
What are the remaining closure properties of Watson-Crick (regular, linear, and context-free) grammars? These depend on their generative capacity.Moreover, there are many interesting topics for further research; for instance, we can define WK context-free and regulated WK context-free grammars and use them in the study of DNA properties and in the DNA based applications such as food authentication and disease gene detection.



---

*Source: 9481971-2016-08-29.xml*