• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Gramatyka formalna



    Podstrony: [1] 2 [3]
    Przeczytaj także...
    Analizator składniowy lub parser – program dokonujący analizy składniowej danych wejściowych w celu określenia ich struktury gramatycznej w związku z określoną gramatyką formalną. Nazwa analizator składniowy podkreśla analogię z analizą składniową stosowaną w gramatyce i językoznawstwie. Analizator składniowy umożliwia przetworzenie tekstu czytelnego dla człowieka w strukturę danych przydatną dla oprogramowania komputera.Gramatyka kombinatoryczna – gramatyka formalna bez ograniczeń na postać reguł. W hierarchii Chomsky’ego jest to gramatyka typu 0. Generuje język rekurencyjnie przeliczalny.
    Symbole terminalne i nieterminalne[ | edytuj kod]

    Nie ogranicza nas też specjalnie podział na symbole terminalne i nieterminalne. Jeśli chcemy możemy nawet wymagać, żeby po lewej stronie każdej reguły były tylko symbole nieterminalne.

    Jeśli mamy w którymś miejscu symbol terminalny a chcemy mieć tam symbol nieterminalny, to tworzymy specjalny symbol nieterminalny i regułę Wtedy wszędzie oprócz tej reguły zamiast używamy

    Modelowanie matematyczne to użycie języka matematyki do opisania zachowania jakiegoś układu (na przykład układu automatyki, biologicznego, ekonomicznego, elektrycznego, mechanicznego, termodynamicznego).Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.

    Dla przykładu, załóżmy że mamy gramatykę:

  • I chcemy żeby po lewej stronie były tylko symbole nieterminalne. Dodajemy więc następujące reguły:

    Symbol startowy to symbol nieterminalny wyróżniony w konkretnej gramatyce formalnej, taki że generację słowa w tej gramatyce zaczynamy od słowa złożonego z tego symbolu.Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci:
  • A te już istniejące zamieniamy na:

    Gemeinsame Normdatei (GND) – kartoteka wzorcowa, stanowiąca element centralnego katalogu Niemieckiej Biblioteki Narodowej (DNB), utrzymywanego wspólnie przez niemieckie i austriackie sieci biblioteczne.
  • Tej techniki używa się np. w budowaniu postaci normalnej Chomsky’ego gramatyk bezkontekstowych.

    Alternatywa języków[ | edytuj kod]

    Załóżmy że mamy gramatykę generującą język i generującą język chcemy uzyskać język wszystkich słów które są albo w albo w

    W tym celu tworzymy symbol startowy i dodajemy reguły przepisania go na symbol startowy pierwszego bądź drugiego języka: Oraz wszystkie reguły z obu gramatyk.

    Słowo będzie więc należało do języka jeśli da się wyprowadzić w jednej z gramatyk. Musimy jednak zadbać o to, żeby nie wolno było mieszać wyprowadzeń – tak, że część słowa jest wyprowadzona pierwszą gramatyką, a część drugą. Zanim więc połączymy zbiory reguł obu gramatyk, przekształćmy je najpierw tak, żeby po lewej stronie wszystkich reguł były wyłącznie nieterminale, i zmieńmy nazwy wszystkich nieterminali, żeby żaden nieterminal nie występował jednocześnie w obu gramatykach (to jak nazwane będą nieterminale nie wpływa w żaden sposób na to, jaki język dana gramatyka generuje). Jeśli gramatyki są tej postaci, to w żaden sposób nie da się w jednym wyprowadzeniu użyć reguł obu gramatyk.

    Algorytm taki nie istnieje dla dopełnienia języka (zbioru wszystkich słów które nie należą do danego języka). Jest nawet możliwe, że dany język opisuje jakaś gramatyka, ale dla zbioru słów nie należących do niego nie ma żadnej gramatyki.

    Dla dwóch gramatyk potrafimy też znaleźć gramatykę przecięcia języków (zbioru słów należących do obu języków), ale jej postać może być o wiele trudniejsza od postaci gramatyk oryginalnych.

    Podstrony: [1] 2 [3]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.018 sek.