Wbudowany automat push-down

Wbudowany automat przesuwający w dół lub EPDA to model obliczeniowy do analizowania języków generowanych przez gramatyki sąsiadujące z drzewem (TAG). Jest podobny do automatu rozkładającego gramatykę bezkontekstową , ale zamiast używać zwykłego stosu do przechowywania symboli, ma stos iterowanych stosów, które przechowują symbole, dając TAG-om zdolność generatywną między gramatyką bezkontekstową i kontekstową lub podzbiór lekko kontekstowych gramatyk . Wbudowanych automatów przesuwających w dół nie należy mylić z zagnieżdżonymi automatami stosowymi , które mają większą moc obliczeniową.

Historia i zastosowania

EPDA zostały po raz pierwszy opisane przez K. Vijaya-Shankera w jego rozprawie doktorskiej z 1988 roku. Od tego czasu zostały zastosowane do pełniejszych opisów klas gramatyk lekko kontekstowych i odegrały ważną rolę w udoskonalaniu hierarchii Chomsky'ego . W ten sposób można zdefiniować różne podgramatyki, takie jak gramatyka indeksowana liniowo .

Podczas gdy języki naturalne były tradycyjnie analizowane przy użyciu gramatyk bezkontekstowych (patrz gramatyka transformacyjno-generatywna i lingwistyka komputerowa ), model ten nie działa dobrze w przypadku języków z krzyżowymi zależnościami, takich jak niderlandzki, w sytuacjach, w których EPDA jest dobrze przystosowana. Szczegółowa analiza językowa jest dostępna w Joshi, Schabes (1997).

Teoria

EPDA to skończona maszyna stanów ze zbiorem stosów, do których można uzyskać dostęp poprzez osadzony stos . Każdy stos zawiera elementy alfabetu stosu , więc definiujemy element stosu przez $, \ sigma _ {i} \ in \ Gamma ^ { *}}$${ \ Displaystyle$ , gdzie gwiazda jest zamknięciem alfabetu Kleene .

${\ Displaystyle \, \ Upsilon _ {j} = \ ddagger \ sigma _ {j} = \ {\ sigma _ {j, k}, \ sigma _ {j , k-1}, \ ldots, \ sigma _ {j, 1} \}}$ elementów, więc oznaczamy ten stos w $automacie$ za pomocą symbolu podwójnego sztyletu: , gdzie ${\ Displaystyle \, \ sigma _ {j, k}}$ byłby następnym dostępnym symbolem w stosie. Osadzony stos stosów można $\ Displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$ oznaczyć przez $}$ .

Definiujemy EPDA przez siódemkę (7-tuple)

${\ Displaystyle \, M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, Q _ {\ textrm {F}} ,\sigma _{0})}$ gdzie

• ${\ displaystyle \, Q}$ to skończony zbiór stanów ;
• ${\ Displaystyle \, \ Sigma}$ jest skończonym zbiorem alfabetu wejściowego ;
• ${\ Displaystyle \, \ Gamma}$ to skończony alfabet stosu ;
• ${\ Displaystyle \, q_ {0} \ w Q}$ jest stanem początkowym ;
• ${\ Displaystyle \, Q _ {\ textrm {F}} \ subseteq Q}$ jest zbiorem stanów końcowych ;
• ${\ Displaystyle \, \ sigma _ {0} \ in \ Gamma}$ to początkowy symbol stosu
• ${\ Displaystyle \, \ delta: Q \ razy \ Sigma \ razy \ Gamma \ rightarrow S}$ jest funkcją przejścia , gdzie ${\ Displaystyle \, S}$ są skończonymi podzbiorami ${\ Displaystyle \, Q \ razy (\ ddagger \ Gamma ^ {+}) ^ {*} \ razy \ Gamma ^ {*} \ razy (\ ddagger \Gamma ^{+})^{*}}$ .

W ten sposób funkcja przejścia przyjmuje stan, następny symbol ciągu wejściowego i górny symbol bieżącego stosu i generuje następny stan, stosy, które mają zostać wypchnięte i wyrzucone na osadzony stos, wypychanie i wyskakiwanie bieżącego stosu , oraz stosy, które zostaną uznane za bieżące stosy w następnym przejściu. Bardziej koncepcyjnie, osadzony stos jest wypychany i zdejmowany, bieżący stos jest opcjonalnie wypychany z powrotem na osadzony stos , a wszelkie inne stosy, które chcesz, są wypychane na wierzch, przy czym ostatni stos jest tym, z którego odczytuje się w następnej iteracji . Dlatego stosy można przesuwać zarówno powyżej, jak i poniżej bieżącego stosu.

Dana konfiguracja jest zdefiniowana przez

${\ Displaystyle \, C (M) = \ {q, \ Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\w Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{ *}\razy \Sigma ^{*}}$

gdzie $, q}$ \ to aktualny stan, s to stosy w osadzonym stosie , z bieżącym $\$$, \ Upsilon _ {m}}$ stos i dla ciągu wejściowego ${\ Displaystyle \, x = x_ {1} x_ {2} \ in \ Sigma ^ {*}}$ , ${\ Displaystyle \, x_ { 1}}$ to część łańcucha już przetworzona przez maszynę, a $część$ przetworzenia, której nagłówek jest aktualnie odczytanym symbolem. Zauważ, że pusty ciąg jest domyślnie zdefiniowany jako symbol kończący, gdzie jeśli maszyna jest w stanie końcowym, gdy odczytywany jest pusty ciąg, cały ciąg wejściowy jest akceptowany $\ Sigma}$ , a jeśli nie, jest odrzucany . Takie akceptowane ciągi są elementami języka

${\ Displaystyle \, L (M) = \ lewo \ {x | \ {q_ {0}, \Upsilon _{0},\epsilon,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x ,\epsilon \}\prawo\}}$

gdzie ${\ Displaystyle \, q _ {\ textrm {F}} \ w Q _ {\ textrm {F}}}$ i ${\ Displaystyle \, \ rightarrow _ {M} ^ {*}}$ definiuje funkcję przejścia stosowaną tyle razy, ile potrzeba do przeanalizowania łańcucha.

Nieformalny opis EPDA można również znaleźć w Joshi, Schabes (1997), Sect.7, s. 23-25.

k -rząd EPDA i hierarchia Weira

Dokładniej zdefiniowaną hierarchię języków, która odpowiada klasie lekko zależnej od kontekstu, zdefiniował David J. Weir. Oparta na pracy Nabila A. Khabbaza, Weir's Control Language Hierarchy to hierarchia zawierająca policzalny zestaw klas językowych , gdzie poziom 1 jest zdefiniowany jako bezkontekstowy, a poziom 2 to klasa przylegająca do drzewa i pozostałe trzy gramatyki.

Poniżej przedstawiono niektóre właściwości języków poziomu k w hierarchii:

• poziomu k są właściwie zawarte w klasie języków poziomu ( k + 1).
• poziomu k można analizować w czasie ${\ Displaystyle O (n ^ {3 \ cdot 2 ^ {k-1}})}$
• Poziom- k zawiera język ${\ Displaystyle \ {a_ {1} ^ {n} \ kropka a_ {2 ^ {k}} ^ {n} | n \ geq 0 \}}, ale$ nie ${\ Displaystyle \ {a_ {1} ^ {n} \ kropka a_ {2 ^ {k + 1}} ^ {n} | n \ geq 0 \}}$
• Poziom- k zawiera język ${\ Displaystyle \ {w ^ {2 ^ {k-1}} | w \ w \ {a, b \} ^ {*} \}} , ale$ nie ${\ Displaystyle \ {w ^ {2 ^ {k-1} + 1} | w \ w \ {a, b \} ^ {*} \}}$

Właściwości te dobrze odpowiadają (przynajmniej dla małego k > 1) warunkom lekko kontekstowych języków narzuconych przez Joshiego, a wraz ze wzrostem k klasa językowa staje się w pewnym sensie mniej wrażliwa na kontekst.

Zobacz też

• kombinatoryczna gramatyka kategorialna

Dalsza lektura

•   Laura Kallmeyer (2010). Analiza poza gramatyką bezkontekstową . Springer Science & Business Media. ISBN 978-3-642-14846-0 .