Gramatyka kategorialna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Gramatyka kategorialna – rodzaj gramatyki formalnej, w której wyróżnia się: słownik będący zbiorem atomów języka opisywanego przez gramatykę, typizację początkową określającą zasady przypisywania typów elementom ze słownika oraz typ naczelny gramatyki. Teoria gramatyk kategorialnych zajmuje się zatem różnymi metodami opisu języków symbolicznych i języka naturalnego, opartymi na typizacji języka.

Podstawowe zasady[edytuj | edytuj kod]

  1. Zasada funktorowości – wyrażenia złożone języka składają się z pewnej części głównej (funktora) oraz części uzupełniającej (argumentów). Dla przykładu, w wyrażeniu Wojtek widzi słonia wyraz widzi jest funktorem, zaś argumentami wyrazy Wojtek i słonia.
  2. Zasada typizacji – kategorię syntaktyczną wyrażenia określa przyporządkowany temu wyrażeniu typ.
  3. Zasada atomiczności – typ wyrażenia złożonego jest funkcją typów wyrażeń atomowych wchodzących w skład tego wyrażenia.
  4. Zasada zastępowalności – dwa wyrażenia należą do tej samej kategorii wtedy i tylko wtedy, gdy każde poprawnie zbudowane wyrażenie, zawierające jedno z nich, nie przestaje być poprawnie zbudowanym wyrażeniem (nie zmienia swojej kategorii) po zastąpieniu jednego przez drugie. Kategorią syntaktyczną będziemy nazywać zbiór wyrażeń wzajemnie zastępowalnych z zachowaniem poprawności gramatycznej. Przykładowo, wyrazy słonia i bażanta należą do jednej kategorii syntaktycznej, gdyż zawsze możemy zastąpić jeden z tych wyrazów drugim bez utraty poprawności syntaktycznej (np. Wojtek widzi słonia \to Wojtek widzi bażanta).

Definicje pomocnicze[edytuj | edytuj kod]

Struktury i języki funktorowe

Niech FS(V) oznacza zbiór wszystkich struktur funktorowych nad V. FS(V) określamy jako najmniejszy zbiór spełniający następujące warunki:

  1. V ∈ FS(V)
  2. Jeżeli A1,...,An ∈ FS(V), gdzie n≥2, to (A1...An)i ∈ FS(V), dla każdego 1≤i≤n.

,gdzie zbiór V jest zbiorem atomów.

Dowolny zbiór struktur funktorowych nad V nazywamy językiem funktorowym nad V.

Typy i typizacje

Ustalmy przeliczalny, nieskończony zbiór stałych Pr, którego elementy nazywamy typami pierwotnymi. Określamy: Tp = FS(Pr). Elementy zbioru Tp nazywamy typami (typy spoza Pr nazywamy typami funktorowymi).

Definicja intuicyjna:
Typizacja polega na przyporządkowaniu wyrażeniu funktorowemu pewnego zbioru typów, będącego podzbiorem zbioru typów powstałego z zbioru typów pierwotnych oraz typów funktorowych.

Typizacją zbioru FS(V) nazywamy dowolną funkcję T określoną na FS(V), która każdej strukturze A ∈ FS(V) przyporządkowuje pewien zbiór T(A) ⊆ Tp (T(A) może być pusty).

Dla dowolnej typizacji T na FS(V) określamy:

  • TYP(T) = {x ∈ Tp: x ∈ T(A), dla pewnego A ∈ FS(V)}

Typizację T nazywamy skończoną jeżeli zbiór TYP(T) jest skończony, a jednoznaczną – jeżeli dla każdej

Definicja intuicyjna:
Zbiór TYP(T) – zbiór typów, które dana typizacja może przyporządkować pewnej strukturze funktorowej A.

struktury A ∈ FS(V) zbiór T(A) zawiera najwyżej jeden typ; piszemy wówczas: T(A) = x zamiast: x ∈ T(A).

Klasyczne gramatyki kategorialne (w sensie LeśniewskiegoAjdukiewicza – Bar-Hillela) – formalna definicja[edytuj | edytuj kod]

Gramatyka kategorialna to trójka G = (VG, IG, sG), taka że:

  • VG jest zbiorem atomów,
  • IG jest typizacją na FS(VG), dla której IG(A) = Ø, jeśli A ∈ VG, sG ∈ Pr.

VG, IG, sG nazywamy kolejno: słownikiem, typizacją początkową i typem naczelnym gramatyki G.

Przykład[edytuj | edytuj kod]

Język LA jest to język złożony z poprawnie zbudowanych równości arytmetycznych; zbiór atomów języka LA jest sumą zbioru NA będącego zbiorem nazw liczb naturalnych i zbioru {+,·,=}. Zbiór termów języka LA (TERA) jest najmniejszym zbiorem spełniającym następujące warunki:

  • NA ⊆ TERA
  • Jeżeli A, B ∈ TERA to (A + B)2, (A · B)2 ∈ TERA

Do języka LA należą też struktury postaci (A = B)2, gdzie A, B ∈ TERA.

Strukturom z LA przypisujemy typ s, strukturom z TERA – typ n. Symbole + i · są funktorami języka które w połączeniu z dwiema strukturami typu n (symbol + lub · umieszczamy pomiędzy struktury typu n) tworzą nową strukturę typu n – otrzymują zatem typ (nnn)2. Symbol = umieszczony pomiędzy strukturami typu n tworzy strukturę typu s – otrzymuje typ (nsn)2.

Gramatyką kategorialną (w sensie Leśniewskiego – Ajdukiewicza – Bar-Hillela) określającą język LA jest gramatyka G postaci: G = (VA, IA, s), gdzie:

  • VA = NA
  • IA(v) = n, dla v ∈ NA; IA(+) = IA(·) = (nnn)2; IA(=) = (nsn)2

Znaczenia i zastosowanie gramatyk kategorialnych[edytuj | edytuj kod]

I logika

  • analiza roli typów w składni i semantyce języka

II lingwistyka

  • ustanowienie wzorca formalizacji języka
  • maszynowa analiza syntaktyczna
  • przekład maszynowy

Bibliografia[edytuj | edytuj kod]

  1. Logiczne podstawy gramatyk kategorialnych Ajdukiewicza-Lambeka, Wojciech Buszkowski (Wydawnictwo PWN, Warszawa 1989, ISBN 83-01-08319-0)