Język formalny

Język formalny – podzbió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

Język formalny ${\displaystyle L}$ to zbiór łańcuchów wybranych z pewnego ${\displaystyle \Sigma ^{*},}$ gdzie ${\displaystyle \Sigma }$ jest konkretnym alfabetem. Jeśli ${\displaystyle \Sigma }$ jest alfabetem i ${\displaystyle L\subseteq \Sigma ^{*}}$ to L jest zwany językiem nad ${\displaystyle \Sigma .}$ Język nad ${\displaystyle \Sigma }$ nie musi obejmować wszystkich łańcuchów zawierających wszystkie symbole z ${\displaystyle \Sigma .}$ Więc gdy ${\displaystyle L}$ jest językiem nad ${\displaystyle \Sigma ,}$ jest on językiem nad dowolnym alfabetem będącym podzbiorem nad ${\displaystyle \Sigma }$^[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

Alfabet to dowolny, niepusty zbiór symboli. Zazwyczaj alfabet oznaczamy symbolem ${\displaystyle \Sigma }$^[2].

• ${\displaystyle \Sigma =\lbrace 1,0\rbrace }$ alfabet binarny
• ${\displaystyle \Sigma =\lbrace a,b,...,z\rbrace }$ 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^[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 ${\displaystyle \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. ${\displaystyle \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 ${\displaystyle \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 Chomskiego 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 ${\displaystyle \to }$ 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 ${\displaystyle A,}$ ${\displaystyle B}$ i ${\displaystyle C,}$
• symbolem startowym jest ${\displaystyle A,}$
• reguły przepisywania to:
  • ${\displaystyle A\to BC}$
  • ${\displaystyle A\to CB}$
  • ${\displaystyle B\to 0B0}$
  • ${\displaystyle C\to 1C1}$
  • ${\displaystyle B\to 0}$
  • ${\displaystyle C\to 1}$

Przykładowe wyprowadzenie słowa ${\displaystyle 00011111}$ w tej gramatyce:

• ${\displaystyle A}$
• ${\displaystyle BC}$ ${\displaystyle (A\to BC)}$
• ${\displaystyle 0B0C}$ ${\displaystyle (B\to 0B0)}$
• ${\displaystyle 0B01C1}$ ${\displaystyle (C\to 1C1)}$
• ${\displaystyle 0B011C11}$ ${\displaystyle (C\to 1C1)}$
• ${\displaystyle 00011C11}$ ${\displaystyle (B\to 0)}$
• ${\displaystyle 00011111}$ ${\displaystyle (C\to 1)}$

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 Chomskiego 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

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 Chomskiego. 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.

Przypisy

1. Hopcroft, Motwani i Ullman 2005 ↓, s. 31.
2. Hopcroft, Motwani i Ullman 2005 ↓, s. 29.

Bibliografia

• J.E. Hopcroft, R. Motwani, J.D. Ullman: Wprowadzenie do Teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14502-1.

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

Kontrola autorytatywna (pojęcie w językoznawstwie):

• LCCN: sh85050802
• GND: 4017848-1
• NDL: 00576869
• BnF: 11967270h
• BNCF: 5999
• NKC: ph208851
• J9U: 987007545721205171

Encyklopedie internetowe:

• Britannica: topic/formal-language