Język formalny

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.

Formalna definicja

Aby zdefiniować język formalny, najpierw definiuje się alfabet, wybierając jakiś niepusty zbiór skończony. Elementy tego zbioru nazywane są symbolami. Ciągi symboli, o skończonej długości, nazywane są słowami. Dowolny zbiór takich ciągów nazywany jest językiem formalnym.

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

Alfabetem może być dowolny skończony zbiór. Przykładowe alfabety to:

• zbiór liczb całkowitych należących do jakiegoś przedziału, np. 0 i 1, albo od 0 do 9,
• zbiór wszystkich bądź niektórych liter alfabetu łacińskiego,
• zbiór symboli ASCII,
• zbiór złożony z dokładnie jednego symbolu.
• 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ło by 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

Słowami są dowolne skończone ciągi symboli. 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 $\epsilon$,
• 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. $\pi$ - są.
• nieuporządkowane zbiory symboli, np. zbiór samogłosek.

Języki na zbiorach nieskończonych

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

Dla każdego alfabetu (nawet jednoelementowego), liczba słów nad tym alfabetem jest nieskończona i przeliczalna (oznaczana $\aleph_0$). 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

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 $\rightarrow$ 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

• alfabet składa się z symboli 0 i 1,
• symbole pomocnicze to $A$, $B$ i $C$,
• symbolem startowym jest $A$,
• reguły przepisywania to:
  • $A \rightarrow BC$
  • $A \rightarrow CB$
  • $B \rightarrow 0B0$
  • $C \rightarrow 1C1$
  • $B \rightarrow 0$
  • $C \rightarrow 1$

Przykładowe wyprowadzenie słowa $00011111$ w tej gramatyce:

• $A$
• $BC$ ($A \rightarrow BC$)
• $0B0C$ ($B \rightarrow 0B0$)
• $0B01C1$ ($C \rightarrow 1C1$)
• $0B011C11$ ($C \rightarrow 1C1$)
• $00011C11$ ($B \rightarrow 0$)
• $00011111$ ($C \rightarrow 1$)

Należenie słowa do języka

Nie istnieje ogólna metoda, która dla danej gramatyki formalej 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:

• Gramatyki regularne – rozpoznawalne przez automaty skończone,
• Gramatyki bezkontekstowe – rozpoznawalne przez automaty ze stosem,
• Gramatyki kontekstowe – rozpoznawalne przez automaty liniowo ograniczone,
• Dowolne gramatyki – w ogólności nierozpoznawalne automatycznie. Ich podzbiór, rozpoznawalny przez maszyny Turinga, definiuje klasę języków określanych jako rekurencyjne.

Języki formalne a języki naturalne

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 Chomskyego. 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)^{[potrzebne źródło]}. Lepsze wyniki zostały osiągnięte w tłumaczeniu tekstów specjalistycznych.

Linki zewnętrzne

• Języki, automaty i obliczenia (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
• Semantyka i weryfikacja programów (materiały dydaktyczne MIMUW na studia informatyczne II stopnia)