Język formalny

Język formalny – 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. Alfabet języka formalnego składa się z symboli, słów, lub tokenów których konkatenacje stanowią łańcuchy języka.

Formalna definicja 
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 .

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 
Alfabet to dowolny, niepusty zbór symboli. Zazwyczaj alfabet oznaczamy symbolem .
  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 
Słowami (zwanymi także łańuchami) są dowolne skończone ciągi symboli wybrane z jakiegoś alfabetu. 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 
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 ). 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  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   i 
 symbolem startowym jest 
 reguły przepisywania to:
 
 
 
 
 
 

Przykładowe wyprowadzenie słowa  w tej gramatyce:

Przynależność słowa do języka 
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:
 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 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). Lepsze wyniki zostały osiągnięte w tłumaczeniu tekstów specjalistycznych.

Przypisy

Bibliografia

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)
  Formal languages and systems , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].