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 oraz językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego oraz 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 oraz występujących w pewnym słowniku,
• zbiór takich słów złożonych z cyfr od 0 do 9, które powodują liczbę pierwszą,
• zbiór słów złożonych z zer oraz 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 oraz uruchomieniu zawieszą dany komputer,
• zbiór pusty.

Alfabet

Alfabetem bywa dowolny skończony zbiór. Przykładowe alfabety to:

• zbiór liczb całkowitych należących do jakiegoś przedziału, np. 0 oraz 1, albo od 0 do 9,
• zbiór wszystkich bądź poniektó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 oraz liczbie kolorów.

Alfabetami nie potrafią 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 – oraz 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 zawiera w sobie litery),
• słowo puste (nad dowolnym alfabetem), oznaczane ,
• liczba zapisana w systemie dziesiętnym (jeśli alfabet zawiera w sobie cyfry arabskie) albo rzymskim (jeśli alfabet zawiera w sobie 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 oraz 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 pewnych 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 da się obejść, jeśli tylko zbiór używanych elementów jest przeliczalny. Wtedy te elementy da się 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, trzeba 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 oraz przeliczalna (oznaczana ). Liczba zbiorów słów (liczba języków), jest zatem nieprzeliczalna. Gdyż 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ę zaledwie wybrane klasy języków. Dla przykładu 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

 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 potrafią występować symbole terminalne oraz nieterminalne.

Do tak opisanego języka trzeba 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 da się 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 oraz 1,
• symbole pomocnicze to , oraz ,
• symbolem startowym jest ,
• reguły przepisywania to:
  • 
  • 
  • 
  • 
  • 
  • 

Przykładowe wyprowadzenie słowa w tej gramatyce:

• 
• ()
• ()
• ()
• ()
• ()
• ()

Należenie słowa do języka

Nie istnieje ogólna metoda, która dla danej gramatyki formalej oraz danego słowa pozwoliłaby stwierdzić, czy dane słowo trzeba do języka opisywanego przez tę gramatykę. Wynika to z faktu, że gramatyki formalne potrafią w szczególności definiować zachowanie maszyny Turinga oraz 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 da się 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

 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 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, dopuszcza jednak zrozumieć treść oraz 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 oraz obliczenia (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
• Semantyka oraz weryfikacja programów (materiały dydaktyczne MIMUW na studia informatyczne II stopnia)