Definition
A Matrix Grammar, M G , is a four-tuple G = ( N , T , M , S ) where
1.- N is an alphabet of non-terminal symbols
2.- T is an alphabet of terminal symbols disjoint with N
3.- M = m 1 , m 2 , . . . , m n is a finite set of matrices, which are non-empty sequences m i = [ p i 1 , . . . , p i k ( i ) ] , with k ( i ) ≥ 1 , and 1 ≤ i ≤ n , where each p i j 1 ≤ j ≤ k ( i ) , is an ordered pair p i j = ( L , R ) being L ∈ ( N ∪ T ) ∗ N ( N ∪ T ) ∗ , R ∈ ( N ∪ T ) ∗ these pairs are called "productions", and are denoted L → R . In these conditions the matrices can be written down as m i = [ L i 1 → R i 1 , . . . , L i k ( i ) → R i k ( i ) ]
4.- S is the start symbol
Definition
Let M G = ( N , T , M , S ) be a matrix grammar and let P the collection of all productions on matrices of M G . We said that M G is of type i according to Chomsky's hierarchy with i = 0 , 1 , 2 , 3 , or "increasing length" or "linear" or "without λ -productions" if and only if the grammar G = ( N , T , P , S ) has the corresponding property.
Note: taken from Abraham 1965, with change of nonterminals namesThe context-sensitive language L ( G ) = { a n b n c n : n ≥ 1 } is generated by the C F M G G = ( N , T , M , S ) where N = { S , A , B , C } is the non-terminal set, T = { a , b , c } is the terminal set, and the set of matrices is defined as M : [ S → a b c ] , [ S → a A b B c C ] , [ A → a A , B → b B , C → c C ] , [ A → a , B → b , C → c ] .
Basic concepts
Definition
A Time Variant Grammar is a pair ( G , v ) where G = ( N , T , P , S ) is a grammar and v : N → 2 P is a function from the set of natural numbers to the class of subsets of the set of productions.
Basic concepts
A Programmed Grammar is a pair ( G , s ) where G = ( N , T , P , S ) is a grammar and s , f : P → 2 P are the success and fail functions from the set of productions to the class of subsets of the set of productions.
Definition
A Grammar With Regular Control Language, G W R C L , is a pair ( G , e ) where G = ( N , T , P , S ) is a grammar and e is a regular expression over the alphabet of the set of productions.
Consider the CFG G = ( N , T , P , S ) where N = { S , A , B , C } is the non-terminal set, T = { a , b , c } is the terminal set, and the productions set is defined as P = { p 0 , p 1 , p 2 , p 3 , p 4 , p 5 , p 6 } being p 0 = S → A B C p 1 = A → a A , p 2 = B → b B , p 3 = C → c C p 4 = A → a , p 5 = B → b , and p 6 = C → c . Clearly, L ( G ) = { a ∗ b ∗ c ∗ } . Now, considering the productions set P as an alphabet (since it is a finite set), define the regular expression over P : e = p 0 ( p 1 p 2 p 3 ) ∗ ( p 4 p 5 p 6 ) .
Combining the CFG grammar G and the regular expression e , we obtain the CFGWRCL ( G , e ) = ( G , p 0 ( p 1 p 2 p 3 ) ∗ ( p 4 p 5 p 6 ) ) which generates the language L ( G ) = { a n b n c n : n ≥ 1 } .
Besides there are other grammars with regulated rewriting, the four cited above are good examples of how to extend context-free grammars with some kind of control mechanism to obtain a Turing machine powerful grammatical device.
