A matrix grammar is a formal grammar in which instead of single productions, productions are grouped together into finite sequences. A production cannot be applied separately, it must be applied in sequence. In the application of such a sequence of productions, the rewriting is done in accordance to each production in sequence, the first one, second one etc. till the last production has been used for rewriting. The sequences are referred to as matrices .
Matrix grammar is an extension of context-free grammar , and one instance of a controlled grammar .
Formal definition [ edit ] A matrix grammar is an ordered quadruple
G
=
(
V
N
,
V
T
,
X
0
,
M
)
{\displaystyle G=(V_{N},V_{T},X_{0},M)}
V
N
{\displaystyle V_{N}}
V
T
{\displaystyle V_{T}}
X
0
{\displaystyle X_{0}}
V
N
{\displaystyle V_{N}}
M
{\displaystyle M}
(
P
,
Q
)
{\displaystyle (P,Q)}
P
∈
V
∗
V
N
V
∗
,
Q
∈
V
∗
,
V
=
V
N
∪
V
T
.
{\displaystyle \quad P\in V^{*}V_{N}V^{*},\quad Q\in V^{*},\quad V=V_{N}\cup V_{T}.}
[1]
productions , written as
P
→
Q
{\displaystyle P\to Q}
matrices and can be written as
m
=
[
P
1
→
Q
1
,
…
,
P
r
→
Q
r
]
.
{\displaystyle m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].}
Let
F
{\displaystyle F}
m
{\displaystyle m}
G
{\displaystyle G}
G
{\displaystyle G}
i
,
i
=
0
,
1
,
2
,
3
{\displaystyle i,i=0,1,2,3}
length-increasing , linear ,
λ
{\displaystyle \lambda }
context-free or context-sensitive if and only if the grammar
G
1
=
(
V
N
,
V
T
,
X
0
,
F
)
{\displaystyle G_{1}=(V_{N},V_{T},X_{0},F)}
For a matrix grammar
G
{\displaystyle G}
⇒
G
{\displaystyle \Rightarrow _{G}}
⇒
{\displaystyle \Rightarrow }
P
,
Q
∈
V
∗
{\displaystyle P,Q\in V^{*}}
P
⇒
Q
{\displaystyle P\Rightarrow Q}
r
≥
1
{\displaystyle r\geq 1}
α
1
,
,
…
,
α
r
+
1
,
P
1
,
…
,
P
r
,
Q
1
,
…
,
Q
r
,
R
1
,
…
,
R
r
,
,
R
1
,
…
,
R
r
{\displaystyle \alpha _{1},,\ldots ,\alpha _{r+1},\quad P_{1},\ldots ,P_{r},\quad Q_{1},\ldots ,Q_{r},\quad R_{1},\ldots ,R_{r},\quad ,R^{1},\ldots ,R^{r}}
over V exist and
α
1
=
P
{\displaystyle \alpha _{1}=P}
α
r
+
1
=
Q
{\displaystyle \alpha _{r+1}=Q}
[
P
1
→
Q
1
,
…
,
P
r
→
Q
r
]
{\displaystyle [P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}]}
G
{\displaystyle G}
α
i
=
R
i
P
i
R
i
{\displaystyle \alpha _{i}=R_{i}P_{i}R^{i}}
α
i
+
1
=
R
i
Q
i
R
i
{\displaystyle \alpha _{i+1}=R_{i}Q_{i}R^{i}}
i
{\displaystyle i}
1
≤
i
≤
r
.
{\displaystyle 1\leq i\leq r.}
Let
⇒
∗
{\displaystyle \Rightarrow ^{*}}
⇒
{\displaystyle \Rightarrow }
G
{\displaystyle G}
L
(
G
)
=
{
P
∈
V
T
∗
|
X
0
⇒
∗
P
}
.
{\displaystyle L(G)=\{P\in {V_{T}}^{*}|X_{0}\Rightarrow ^{*}P\}.}
Examples [ edit ] Consider the matrix grammar
G
=
(
{
S
,
X
,
Y
}
,
{
a
,
b
,
c
}
,
S
,
M
)
{\displaystyle G=(\{S,X,Y\},\{a,b,c\},S,M)}
where
M
{\displaystyle M}
m
0
:
[
S
→
X
Y
]
,
m
1
:
[
X
→
a
X
b
,
Y
→
c
Y
]
,
m
2
:
[
X
→
a
b
,
Y
→
c
]
{\displaystyle m_{0}:[S\rightarrow XY],\quad m_{1}:[X\rightarrow aXb,Y\rightarrow cY],\quad m_{2}:[X\rightarrow ab,Y\rightarrow c]}
These matrices, which contain only context-free rules, generate the context-sensitive language
L
=
{
a
n
b
n
c
n
|
n
≥
1
}
.
{\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}.}
a
n
b
n
c
n
{\displaystyle a^{n}b^{n}c^{n}}
A
w
(
a
n
b
n
c
n
)
=
m
0
m
1
n
−
2
m
2
,
∀
n
≥
2
{\displaystyle Aw(a^{n}b^{n}c^{n})=m_{0}m_{1}^{n-2}m_{2},\forall n\geq 2}
A
w
(
a
b
c
)
=
m
0
m
2
{\displaystyle Aw(abc)=m_{0}m_{2}}
This example can be found on pages 8 and 9 of [1]
G
=
(
{
S
,
X
,
Y
,
Z
}
,
{
a
,
b
,
c
}
,
S
,
M
)
{\displaystyle G=(\{S,X,Y,Z\},\{a,b,c\},S,M)}
where
M
{\displaystyle M}
m
0
:
[
S
→
a
b
c
]
,
m
1
:
[
S
→
a
X
b
Y
c
Z
]
,
m
2
:
[
X
→
a
X
,
Y
→
b
Y
,
Z
→
c
Z
]
,
m
3
:
[
X
→
a
b
,
Y
→
b
,
Z
→
c
]
{\displaystyle m_{0}:[S\rightarrow abc],\quad m_{1}:[S\rightarrow aXbYcZ],\quad m_{2}:[X\rightarrow aX,Y\rightarrow bY,Z\rightarrow cZ],\quad m_{3}:[X\rightarrow ab,Y\rightarrow b,Z\rightarrow c]}
These matrices, which contain only context-regular rules, generate the context-sensitive language
L
=
{
a
n
b
n
c
n
|
n
≥
1
}
.
{\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}.}
The associate word of
a
n
b
n
c
n
{\displaystyle a^{n}b^{n}c^{n}}
A
w
(
a
n
b
n
c
n
)
=
m
1
m
2
n
−
2
m
3
,
∀
n
≥
2
{\displaystyle Aw(a^{n}b^{n}c^{n})=m_{1}m_{2}^{n-2}m_{3},\forall n\geq 2}
A
w
(
a
b
c
)
=
m
0
{\displaystyle Aw(abc)=m_{0}}
Properties [ edit ] Let
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
MAT the class of languages produced by
λ
{\displaystyle \lambda }
Trivially, MAT is included in
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
All context-free languages are in MAT , and all languages in
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
recursively enumerable .
MAT is closed under union , concatenation , intersection with regular languages and permutation.All languages in MAT can be produced by a context-sensitive grammar .
There exists a context-sensitive language which does not belong to
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
[2]
Each language produced by a matrix grammar with only one terminal symbol is regular. Open problems [ edit ] It is not known whether there exist languages in
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
MAT , and it is neither known whether
MAT
λ
{\displaystyle {\ce {MAT^{\lambda }}}}
[3]
References [ edit ] ^ [4] ^ 
![{\displaystyle m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4f0cb8cb2a2d38d0fb0a6273430a3b0849c619a)
![{\displaystyle [P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c9623b46bd9f15c050abc72b1dae7304013ca2b)
![{\displaystyle m_{0}:[S\rightarrow XY],\quad m_{1}:[X\rightarrow aXb,Y\rightarrow cY],\quad m_{2}:[X\rightarrow ab,Y\rightarrow c]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95c57900ea361d5dc71611dedfdca381470d2f00)
![{\displaystyle m_{0}:[S\rightarrow abc],\quad m_{1}:[S\rightarrow aXbYcZ],\quad m_{2}:[X\rightarrow aX,Y\rightarrow bY,Z\rightarrow cZ],\quad m_{3}:[X\rightarrow ab,Y\rightarrow b,Z\rightarrow c]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd698e4cd8d6e9dbb14d766966df7bd3cbedf8bf)
