Język formalny

Z Wikipedii, wolnej encyklopedii

Język formalnypodzbiór zbioru wszystkich słów nad skończonym alfabetem[1]. 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. Alfabet języka formalnego składa się z symboli, słów, lub tokenów których konkatenacje stanowią łańcuchy języka.

Formalna definicja[edytuj | edytuj kod]

Język formalny to zbiór łańcuchów wybranych z pewnego gdzie jest konkretnym alfabetem. Jeśli jest alfabetem i to L jest zwany językiem nad Język nad nie musi obejmować wszystkich łańcuchów zawierających wszystkie symbole z Więc gdy jest językiem nad jest on językiem nad dowolnym alfabetem będącym podzbiorem nad [1].

Przykłady języków formalnych:

  • zbiór wszystkich słów złożonych z liter polskiego alfabetu i występujących w pewnym słowniku,
  • zbiór takich słów złożonych z cyfr od 0 do 9, które przedstawiają liczbę pierwszą,
  • zbiór słów złożonych z zer i jedynek, w których zer jest więcej niż jedynek,
  • zbiór prawidłowo napisanych równań matematycznych,
  • zbiór programów, które po skompilowaniu i uruchomieniu zawieszą dany komputer,
  • zbiór pusty.

Alfabet[edytuj | edytuj kod]

Alfabet to dowolny, niepusty zbiór symboli. Zazwyczaj alfabet oznaczamy symbolem [2].

  • alfabet binarny
  • zbiór wszystkich małych liter

Inne przykłady

  • zbiór kart do gry,
  • zbiór złożony z możliwych wartości koloru piksela (trójki liczb całkowitych, od 0 do 255 każda),
  • zbiór wszystkich obrazów możliwych do wyświetlenia przy ustalonej rozdzielczości ekranu i liczbie kolorów.

Alfabetami nie mogą być:

  • zbiór pusty – nie dałoby się z niego ułożyć żadnego słowa. Można jednak rozszerzyć definicję języka formalnego na ten przypadek – wtedy nad takim alfabetem istnieje tylko jedno słowo – słowo puste – i tylko dwa języki – język pusty oraz język zawierający tylko słowo puste,
  • zbiory nieskończone, np. zbiór wszystkich liczb naturalnych czy rzeczywistych.

Słowo[edytuj | edytuj kod]

Słowami (zwanymi także łańuchami) są dowolne skończone ciągi symboli wybrane z jakiegoś alfabetu[2]. Przykładowe słowa to:

  • słowa języka naturalnego, np. „ala”, „słoneczko” (jeśli alfabet obejmuje litery),
  • słowo puste (nad dowolnym alfabetem), oznaczane
  • liczba zapisana w systemie dziesiętnym (jeśli alfabet obejmuje cyfry arabskie) lub rzymskim (jeśli alfabet obejmuje znaki I, V, X, L, C, M, D),
  • wyrażenie algebraiczne,
  • film o dowolnej skończonej długości, wyświetlany na ekranie o ustalonej rozdzielczości i liczbie kolorów (jeśli alfabetem jest zbiór obrazów możliwych do wyświetlenia na tym ekranie).

Słowami nie są:

  • ciągi o nieskończonej długości, np. reprezentacje liczb niewymiernych w systemie dziesiętnym – choć już reprezentacje symboliczne, np. – są.
  • nieuporządkowane zbiory symboli, np. zbiór samogłosek.

Języki na zbiorach nieskończonych[edytuj | edytuj kod]

W niektórych zastosowaniach, przydatne jest operowanie na ciągach elementów z nieskończonego zbioru, np. zbioru liczb naturalnych. Zbiór takich ciągów nie jest językiem, ale to ograniczenie można obejść, jeśli tylko zbiór używanych elementów jest przeliczalny. Wtedy te elementy można przedstawić jako słowa nad skończonym alfabetem.

Przykładowo, aby operować na ciągach liczb naturalnych, zapisuje się te liczby w sposób pozycyjny. Np. ciąg „10 200 317 852”, zawierający 14 symboli, należy do języka ciągów liczb naturalnych zapisanych w postaci pozycyjnej, za pomocą cyfr arabskich oraz spacji.

Metody definiowania języków[edytuj | edytuj kod]

Dla każdego alfabetu (nawet jednoelementowego), liczba słów nad tym alfabetem jest nieskończona i przeliczalna (oznaczana ). Liczba zbiorów słów (liczba języków), jest zatem nieprzeliczalna. Ponieważ każda metoda opisania może objąć tylko przeliczalną liczbę elementów, nie istnieje metoda opisania wszystkich języków nad żadnym niepustym alfabetem. Dlatego opisuje się jedynie wybrane klasy języków. Przykładowo hierarchia Chomsky’ego precyzuje cztery klasy języków, w zależności od tego jak złożona jest gramatyka formalna opisująca dany język.

Gramatyki formalne[edytuj | edytuj kod]

 Osobny artykuł: Gramatyka formalna.

Gramatyki formalne są najpopularniejszym sposobem opisywania języków formalnych. Opis w postaci gramatyki składa się z:

  • Określenia symboli alfabetu, na którym zbudowany jest język. Są to tzw. symbole terminalne.
  • Określenia dowolnego skończonego zbioru symboli pomocniczych, tzw. symboli nieterminalnych
  • Określenia jednego symbolu startowego, należącego do symboli nieterminalnych.
  • Określenia pewnego skończonego zbioru reguł przepisywania (zwanych też produkcjami). Każda reguła, to para słów (lewe prawe), w których mogą występować symbole terminalne i nieterminalne.

Do tak opisanego języka należy każde słowo, dla którego potrafimy zbudować taki ciąg, że:

  • pierwszym elementem ciągu jest słowo złożone z symbolu startowego,
  • każde kolejne słowo w ciągu można uzyskać przez zastąpienie w poprzednim słowie fragmentu równego lewemu słowu jakiejś reguły przez prawe słowo tej reguły,
  • ostatnim elementem ciągu jest dane słowo.

Przykładowa gramatyka[edytuj | edytuj kod]

  • alfabet składa się z symboli 0 i 1,
  • symbole pomocnicze to i
  • symbolem startowym jest
  • reguły przepisywania to:

Przykładowe wyprowadzenie słowa w tej gramatyce:

Przynależność słowa do języka[edytuj | edytuj kod]

Nie istnieje ogólna metoda, która dla danej gramatyki formalnej i danego słowa pozwoliłaby stwierdzić, czy dane słowo należy do języka opisywanego przez tę gramatykę. Wynika to z faktu, że gramatyki formalne mogą w szczególności definiować zachowanie maszyny Turinga i powyższy problem wymagałby rozwiązania problemu stopu. Dlatego w praktycznych zastosowaniach używa się wybranych klas gramatyk, dla których taka weryfikacja jest możliwa do przeprowadzenia. W ogólności, im więcej języków potrafi opisać dana klasa gramatyk, tym problem tej weryfikacji ma większą złożoność.

Przykładowo, hierarchia Chomsky’ego wprowadza podział na następujące klasy, które można zdefiniować przez złożoność automatu rozpoznającego należenie do języka:

Języki formalne a języki naturalne[edytuj | edytuj kod]

 Osobny artykuł: Tłumaczenie automatyczne.

Języki formalne są używane do opisu języków naturalnych, choć nie jest to łatwe. Od 1956 roku stosowane są np. tzw. gramatyki generatywne Chomsky’ego. Problemem jest kontekstowość języka naturalnego, tzn. zależność reguł gramatycznych, a szczególnie reguł interpretacji (semantyki) języka naturalnego od kontekstu, czyli sąsiednich zdań, a nawet wypowiedzi bezpośrednio z daną nie sąsiadujących.

Aktualnie istnieje wiele systemów komercyjnych przetwarzających język naturalny. Tłumaczenie wolnego tekstu jest bardzo niedokładne, pozwala jednak zrozumieć treść i wspomaga pracę tłumaczy (przyspieszenie nawet 4 razy)[potrzebny przypis]. Lepsze wyniki zostały osiągnięte w tłumaczeniu tekstów specjalistycznych.

Przypisy[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]