1 Lingwistyka Matematycznawykład 2

2 Lingwistyka Matematyczna Gramatyka Chomsky’ego Hierarchia Chomsky’ego Agenda Lingwistyka Matematyczna Gramatyka Chomsky’ego Hierarchia Chomsky’ego Notacja BNF Podsumowanie Q&A Mgr inż. Michał Jaros

3 Lingwistyka MatematycznaLingwistyka Matematyczna – dział językoznawstwa, w którym do badania języków stosuje się metody matematyczne, podzielony na dwa kierunki: syntetyczny i analityczny. Kierunek syntetyczny zajmuje się badaniem różnych typów gramatyk formalnych (związany z informatyką). Mgr inż. Michał Jaros

4 Lingwistyka MatematycznaTworzenie języków programowania Budowa analizatorów Budowa translatorów Budowa kompilatorów Mgr inż. Michał Jaros

5 Lingwistyka Matematyczna Mgr inż. Michał Jaros

6 Lingwistyka MatematycznaSłownik – zasób wyrazów (słów) danego języka, podstawa każdego języka. W językach formalnych elementy słownika (słowa) nazywamy symbolami (podstawowymi). Zdanie – ciąg słów zbudowany według określonych reguł. Mgr inż. Michał Jaros

7 Lingwistyka MatematycznaSyntaktyka (składnia) – dział gramatyki zajmujący się budową zdań, badaniem zależności między wyrazami w zdaniu. Badanie struktury języka. Semantyka – dziedzina zajmująca się znaczeniem zdań. Mgr inż. Michał Jaros

8 Lingwistyka MatematycznaJęzyk formalny – język złożony ze wszystkich słów (wyrażeń) uzyskiwanych za pomocą ściśle określonych reguł; definiowany zwykle przez gramatykę formalną. Gramatyka formalna – definicja składni języka. Zbiór reguł lub formuł, które określają zbiór formalnie poprawnych zdań. Mgr inż. Michał Jaros

9 Gramatyka Chomsky’egoNoam Chomsky Język jest według Chomsky'ego nieskończonym zbiorem zdań, generowanych za pomocą skończonej liczby reguł i słów. Bezbarwne zielone idee wściekle śpią. Mgr inż. Michał Jaros

10 Gramatyka Chomsky’egoMatematyczna definicja języka Język L = L ( T, N, P, S ) jest definiowany przez: T – słownik symboli końcowych; N – zbiór symboli pomocniczych; P – zbiór produkcji (reguł syntaktycznych); S – głowa języka, symbol początkowy należący do N; Mgr inż. Michał Jaros

11 Gramatyka Chomsky’egoJęzyk L ( T, N, P, S ) jest zbiorem ciągów symboli końcowych ξ, które mogą być wyprowadzone z S zgodnie z podaną poniżej regułą gdzie, ξ oznacza ciąg symboli T* oznacza zbiór wszystkich ciągów symboli z T Mgr inż. Michał Jaros

12 Gramatyka Chomsky’egoCiąg n może być wyprowadzony z ciągu 0 wtedy i tylko wtedy, gdy istnieją ciągi 1, 2,…., n-1 takie, że każdy ciąg i może być bezpośrednio wyprowadzony z i-1 zgodnie z podaną poniżej regułą Mgr inż. Michał Jaros

13 Gramatyka Chomsky’egoCiąg η może być bezpośrednio wyprowadzony z ξ ciągu wtedy i tylko wtedy gdy istnieją ciągi α, β, ξ’, η’ takie że: ξ = α ξ’ β η = α η’ β P zawiera produkcje ξ’ ::=η’ Mgr inż. Michał Jaros

14 Hierarchia Chomsky’egoHierarchia klas języków formalnych. Typ 0 – Języki rekursywnie przeliczalne Typ 1 – Języki kontekstowe Typ 2 – Języki bezkontekstowe Typ 3 – Języki regularne Mgr inż. Michał Jaros

15 Hierarchia Chomsky’egoJęzyki rekursywnie przeliczalne – języki generowane przez wszystkie gramatyki formalne, zawierające produkcje postaci α → β, gdzie α, β dowolne słowa złożone z nieterminali i terminali. (maszyna Turinga) Mgr inż. Michał Jaros

16 Hierarchia Chomsky’egoJęzyki kontekstowe – języki generowane przez gramatyki kontekstowe, zawierające produkcje postaci αAβ → αγβ, gdzie α, β, γ dowolne słowa złożone z nieterminali i terminali, A – nieterminal S → aBc S → ε aAB → abCB (automat liniowo ograniczony) Mgr inż. Michał Jaros

17 Hierarchia Chomsky’egoJęzyki bezkontekstowe – języki generowane gramatyki bezkontekstowe. S → aBc S → ε A → BC (niedeterministyczny automat ze stosem) Mgr inż. Michał Jaros

18 Hierarchia Chomsky’egoJęzyki regularne – języki generowane przez gramatyki regularne. Mogą być generowane przy pomocy wyrażeń regularnych. S → aB S → ε A → a (automat skończony) Mgr inż. Michał Jaros

19 Notacja BNF (Backus-Naur Form) Notacja BNF jest sposobem zapisu reguł gramatyk, produkcji, czyli sposobem opisu języków formalnych. ::= ::= kwiaty | gwiazdy ::= kwitną | świecą Mgr inż. Michał Jaros

20 Produkcje – reguły poprzez które można zdefiniować język Notacja BNF Produkcje – reguły poprzez które można zdefiniować język Symbol początkowy - Symbole pomocnicze (nieterminalne): , , Symbole końcowe (terminalne): kwiaty, gwiazdy, kwitną, świecą Metasymbole notacji BNF: <, >, ::=, | Mgr inż. Michał Jaros

21 Zdania należące do gramatykiNotacja BNF Gramatyka ::= ::= kwiaty | gwiazdy ::= kwitną | świecą Zdania należące do gramatyki kwiaty kwitną gwiazdy świecą kwiaty świecą gwiazdy kwitną Mgr inż. Michał Jaros

22 Uproszczona notacja BNFS ::= A B A ::= a | b B ::= c | d Zdania należące do gramatyki ac ad bc bd Mgr inż. Michał Jaros

23 Symbole pomocnicze (nieterminalne): wielkie litery alfabetuNotacja BNF Symbol początkowy - S Symbole pomocnicze (nieterminalne): wielkie litery alfabetu Symbole końcowe (terminalne): małe litery alfabetu Mgr inż. Michał Jaros

24 Lingwistyka Matematyczna Gramatyka Chomsky’ego Hierarchia Chomsky’ego Podsumowanie Lingwistyka Matematyczna Gramatyka Chomsky’ego Hierarchia Chomsky’ego Notacja BNF Mgr inż. Michał Jaros

25 Q&A Mgr inż. Michał Jaros

26 KONIEC Mgr inż. Michał Jaros