Gramatyka macierzowa

Gramatyka macierzowa to gramatyka formalna , w której zamiast pojedynczych produkcji, produkcje są grupowane w skończone sekwencje. Produkcji nie można zastosować osobno, należy ją zastosować w sekwencji. Przy zastosowaniu takiej sekwencji produkcji przepisywanie odbywa się zgodnie z każdą kolejną produkcją w kolejności, pierwszą, drugą itd., aż ostatnia produkcja zostanie wykorzystana do przepisywania. Sekwencje są nazywane macierzami .

Gramatyka macierzowa jest rozszerzeniem gramatyki bezkontekstowej i jedną instancją gramatyki kontrolowanej .

Definicja formalna

Gramatyka macierzowa to uporządkowana poczwórna czwórka sol $\ Displaystyle G = (V_ {N}, V_ {T}, X_ {0}, M)}$ gdzie

• ${\ Displaystyle V_ {N}}$ to skończony zbiór nieterminali
• ${\ displaystyle V_ {T}}$ to skończony zbiór terminali
• ${\ displaystyle X_ {0}}$ jest specjalnym elementem ${\ displaystyle V_ {N}}$ , a mianowicie. symbol startowy
• ${\ Displaystyle M}$ to skończony zbiór niepustych sekwencji, których elementami są uporządkowane pary ${\ Displaystyle (P, Q)}$ gdzie

${\ Displaystyle \ quad P \ w V ^ {*} V_ {N} V ^ {*}, \ quad Q \ w V ^ {*}, \ quad V = V_ {N} \ kubek V_ {T}.}$

Pary nazywane są produkcjami , zapisywane jako ${\ displaystyle P \ to Q}$ . Sekwencje nazywane są macierzami i można je zapisać jako

${\ Displaystyle m = [P_ {1} \ do Q_ {1}, \ ldots, P_ {r} \ do Q_ {r}].}$

Niech $będzie$ zbiorem wszystkich produkcji $pojawiających$$w$ macierzowej . Wtedy gramatyka macierzowa jest typu - $\ Displaystyle i, i = 0,1,2,3}$$}$ , zwiększająca długość liniowa , $\lambda }$ -darmowy ${\ Displaystyle G$ , bezkontekstowe lub kontekstowe wtedy i tylko wtedy, gdy gramatyka ${\ Displaystyle G_ {1} = (V_ {N}, V_ {T}, X_ {0} ,F)}$ ma następującą właściwość.

W przypadku gramatyki macierzowej $zdefiniowana$ jest relacja binarna $G}} ;$ reprezentowane również jako ${\ displaystyle \ Rightarrow}$ . Dla każdego ${\ Displaystyle P, Q \ w V ^ {*}}$ , ${\ Displaystyle P \ Rightarrow Q}$ zachodzi wtedy i tylko wtedy, gdy istnieje liczba całkowita ${\ displaystyle r \geq 1}$ takie, że słowa

${\ Displaystyle \ alfa _ {1}, \ ldots, \ alfa _ {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}}$

ponad V istnieje i

• ${\ Displaystyle \ alpha _ {1} = P}$ i ${\ Displaystyle \ alpha _ {r + 1} = Q}$
• ${\ Displaystyle [P_ {1} \ do Q_ {1}, \ ldots, P_ {r} \ do Q_ {r}]}$ jest jedną z macierzy z sol $\ Displaystyle G}$
• $\ Displaystyle \ alfa _ {i} = R_ {i} P_ {i} R ^ {i}}$ i $R_ {i} Q_ {i} R ^ {i}}$${\ Displaystyle \ alfa _ {i + 1}$${\ Displaystyle 1 \ równoważnik ja \ równoważnik r.}$$dla$ wszystkich takich, że

Niech będzie zwrotnym przechodnim zamknięciem relacji $\ Displaystyle$$\ Rightarrow ^ {*}$ } Następnie język generowany przez gramatykę macierzową $jest$ przez

${\ Displaystyle L (G) = \ {P \ w {V_ {T}} ^ {*} | X_ {0} \ Strzałka w prawo ^ {*} P \}.}$

Przykłady

Rozważ gramatykę macierzową

${\ Displaystyle G = (\ {S, X, Y \}, \ {a, b, c \}, S ,M)}$

gdzie jest zbiorem zawierającym następujące macierze: ${\ displaystyle M}$

${\ Displaystyle m_ {0}: [S \ rightarrow XY],\quad m_{1}:[X\rightarrow aXb,Y\rightarrow cY],\quad m_{2}:[X\rightarrow ab,Y\rightarrow c]}$

Te macierze, które zawierają tylko reguły bezkontekstowe , generują język kontekstowy

$.} Powiązane słowo za n b n do n {\$$b ^{n}c^{n}}$ Displaystyle jest ${\ Displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {0} m_ {1} ^ {n-2} m_ {2}, \ forall n \ geq 2 }$ i ${\ Displaystyle Aw (abc) = m_ {0} m_ {2}}$ .

Ten przykład można znaleźć na stronach 8 i 9 w następującej formie: Rozważ gramatykę macierzową

${\ Displaystyle G = (\ {S, X, Y, Z \}, \ {a, b, c \},S,M)}$

gdzie jest zbiorem zawierającym następujące macierze: ${\ displaystyle M}$

${\ 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]}$

Te macierze, które zawierają tylko reguły kontekstowe , generują język kontekstowy

${\ Displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} | n \ geq 1 \}.}$

Za ${\ Displaystyle a ^ {n} b ^ {n} c ^ {n}$${\ Displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {1} m_ {2} ^ {n-2} m_ {3}, \ dla wszystkich n$ to i ${\ Displaystyle Aw (abc) = m_ {0}}$ .

Nieruchomości

Niech $klasą$ będzie klasą języków tworzoną przez gramatyki macierzowe, a $-swobodne$ tworzoną przez gramatyki macierzowe.

• Trywialnie, MAT jest zawarta w ${\ displaystyle {\ ce {MAT ^ {\ lambda}}}}$ .
• Wszystkie języki bezkontekstowe $są$ w MAT , a języki w są rekurencyjnie przeliczalne .
• MAT jest zamknięta na unię , konkatenację , przecięcie z językami regularnymi i permutację.
• Wszystkie języki w MAT mogą być tworzone za pomocą gramatyki kontekstowej .
• Istnieje język kontekstowy, który nie należy do ${\ displaystyle {\ ce {MAT ^ {\ lambda}}}}$ .
• Każdy język utworzony przez gramatykę macierzową z tylko jednym symbolem końcowym jest regularny.

Otwarte problemy

Nie wiadomo, czy w $}}}$ , których nie ma w MAT , i nie wiadomo też, czy ${\lambda }}}}$${\ Displaystyle {\ ce {MAT ^ { \ lambda$ zawiera języki, które nie są zależne od kontekstu.

przypisy

• ^ Ábrahám, S. Niektóre pytania z teorii języka. Międzynarodowa konferencja na temat lingwistyki komputerowej, 1965. s. 1–11. [4]
• ^ Gheorghe Păun, Membrane Computing: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. str. 30–32