Matrix grammar

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. 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. A matrix grammar is an ordered quadruple G = ( V N , V T , X 0 , M ) {displaystyle G=(V_{N},V_{T},X_{0},M)} where P ∈ V ∗ V N V ∗ , Q ∈ V ∗ , V = V N ∪ V T . {displaystyle quad Pin V^{*}V_{N}V^{*},quad Qin V^{*},quad V=V_{N}cup V_{T}.} The pairs are called productions, written as P → Q {displaystyle P o Q} . The sequences are called matrices and can be written as m = [ P 1 → Q 1 , … , P r → Q r ] . {displaystyle m=.} Let F {displaystyle F} be the set of all productions appearing in the matrices m {displaystyle m} of a matrix grammar G {displaystyle G} . Then the matrix grammar G {displaystyle G} is of type- i , i = 0 , 1 , 2 , 3 {displaystyle i,i=0,1,2,3} , length-increasing, linear, λ {displaystyle lambda } -free, 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)} has the following property. For a matrix grammar G {displaystyle G} , a binary relation ⇒ G {displaystyle Rightarrow _{G}} is defined; also represented as ⇒ {displaystyle Rightarrow } . For any P , Q ∈ V ∗ {displaystyle P,Qin V^{*}} , P ⇒ Q {displaystyle PRightarrow Q} holds if and only if there exists an integer r ≥ 1 {displaystyle rgeq 1} such that the words α 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}}