Języki formalne

Język formalny to pewne uogólnienie pojęcia języka, do którego jesteśmy przyzwyczajeni z codziennego życia.

Podstawowe pojęcia

Na początek możemy sobie wyobrazić język formalny jako zwykły język, na przykład polski. Z czego składa się taki język? Ze słów, które dalej łączymy w zdania. Zdania nas nie będą interesować, zajmiemy się tylko słowami. A z czego składają się słowa? Z liter alfabetu. Od alfabetu więc zaczniemy.

Alfabet to dowolny niepusty zbiór. Elementy alfabetu nazywamy symbolami. Jeśli mówimy o języku polskim, będzie to klasyczny polski alfabet obejmujący zarówno małe, jak i wielkie litery, łącznie z literami z ogonkami, kreskami i kropką (ą, ć, ę, ł, ń, ó, ś, ź, ż). Gdybyśmy nie chcieli opisywać polszczyzny, ale na przykład liczby, mielibyśmy w alfabecie wszystkie dziesięć cyfr. Alfabet często oznaczamy symbolem $\Sigma$.

Słowem (inaczej łańcuchem lub napisem) nazywamy skończony ciąg symboli z jakiegoś alfabetu $\Sigma$. Jeśli mamy na przykład alfabet $\Sigma=\left\{a,b,c,d,e,\dots, z\right\}$, to słowem jest na przykład ciąg „ahoj” albo „doberman”, ale już nie „żaba” (nie mamy litery „ż”), „Kasia” (nie mamy litery „K”) ani „dzien dobry” (nie mamy spacji). Długością słowa nazywamy liczbę symboli, z których słowo się składa.

Konkatenacja (złożenie) słów: jeśli mamy dwa słowa a = a₁a₂… a_n i b = b₁b₂… b_m, to ich konkatenacją jest słowo ab = a₁a₂… a_nb₁b₂… b_m. Przykład: konkatenacją słów „ahoj” i „doberman” jest słowo „ahojdoberman”. Konkatenację oznaczamy kółkiem, czyli $a\circ b$, albo nie oznaczamy jej wcale i po prostu zapisujemy słowa jedno za drugim bez specjalnego symbolu.

Słowo puste oznaczamy $\varepsilon$; jest to słowo o długości zerowej. Jeśli złożymy słowo a = a₁… a_n ze słowem pustym $\varepsilon$, otrzymamy z powrotem słowo a. Zachodzi więc $a\circ\varepsilon=a$.

Domknięcie alfabetu $\Sigma$ (domknięcie Kleene’ego) to zbiór wszystkich słów, które potrafimy utworzyć z alfabetu $\Sigma$, łącznie ze słowem pustym. Domknięcie oznaczamy $\Sigma^\ast$. Jeśli mamy alfabet binarny $\Sigma=\left\{0,1\right\}$, to

$$ \Sigma^\ast=\left\{\varepsilon,0{,}1,00{,}01,10{,}11,000{,}001,\dots\right\} $$

Czasem używamy jeszcze domknięcia dodatniego alfabetu, czyli znowu wszystkich słów, które da się złożyć z alfabetu, z wyjątkiem słowa pustego. Domknięcie dodatnie oznaczamy $\Sigma^+$ i zachodzi $\Sigma^+=\Sigma^\ast\setminus\left\{\varepsilon\right\}$.

Przykłady alfabetów

• Wróćmy do przykładu z językiem polskim. Każde polskie słowo znajdziemy w domknięciu alfabetu, który zawiera małe i wielkie litery oraz litery ze znakami diakrytycznymi (plus może jeszcze łącznik „-”). Jeśli do tego alfabetu dodamy jeszcze spację i znaki interpunkcyjne (przecinek, kropka, wykrzyknik, znak zapytania, …), w domknięciu dostaniemy wszystkie zdania, jakie potrafimy utworzyć po polsku. Oczywiście w tym domknięciu będą też zdania w rodzaju „sadflsf kasdf kagrjewiczźąśłóęker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, które jednak bywają bardziej sensowne niż niejedno przemówienie polityka.

• Jeśli nasz alfabet będzie zawierać wszystkie cyfry $\Sigma=\left\{0, 1, \dots, 9\right\}$, to w domknięciu znajdą się wszystkie liczby naturalne – i jeszcze trochę więcej. Będą tam bowiem także liczby zaczynające się od zera, np. 00054, samo zero, a do tego słowo puste, które oczywiście żadną liczbą nie jest.

• Alfabet musi być niepusty, więc najmniejszy alfabet ma co najmniej jeden symbol. Na przykład dla alfabetu $\Sigma=\left\{!\right\}$ otrzymalibyśmy domknięcie $\Sigma^\ast=\left\{\varepsilon, !, !!, !!!, !!!!, \dots\right\}$, czyli zbiór słów, w którym dla każdego n∈ℕ₀ istnieje słowo mające n wykrzykników i nie ma w nim żadnego innego słowa.

• Niech $\Sigma=\left\{qw,c\right\}$. To bardzo dziwny alfabet, bo zawiera słowo qw. Takiego zapisu zwykle się nie używa, bo jest mylący i dziwny, ale możemy to sobie wyobrazić tak, że sklejamy litery „q” i „w” ze sobą, tak że tworzą jeden znak. Wtedy słowo „qw” możemy widzieć jako symbol „qw”. Gdybyśmy z tego symbolu utworzyli słowo „qwcqw”, to miałoby ono długość trzy – składałoby się z symboli „qw”, „c” i „qw”. Z takimi alfabetami nie spotkamy się zbyt często, ale istnieją sytuacje, w których symbole złożone z kilku symboli są potrzebne.

Język formalny

Język (formalny) nad alfabetem $\Sigma$ to dowolny podzbiór $\Sigma^\ast$. Dla języka L nad alfabetem $\Sigma$ zachodzi więc $L\subseteq\Sigma^\ast$. Przykłady języków:

• W poprzedniej części zdefiniowaliśmy alfabet cyfr $\Sigma=\left\{0, 1, \dots, 9\right\}$. Jego domknięciem są wszystkie słowa utworzone wyłącznie z cyfr. Jeśli dodamy regułę, że słowo nie może zaczynać się od zera i nie może być puste, otrzymamy zbiór liczb naturalnych ℕ. Zachodzi $\mathbb{N}\subseteq\Sigma^\ast$, więc ℕ jest językiem nad alfabetem $\Sigma$.

• Do poprzedniego zbioru cyfr możemy jeszcze dodać znak minus „-”, czyli $\Sigma=\left\{0, 1, \dots, 9, -\right\}$. Domknięciem są wszystkie słowa złożone z cyfr lub znaku minus. To jednak oznacza, że w domknięciu są też słowa takie jak „12-84-”, „1-5-8” albo „-”. Język liczb całkowitych ℤ utworzymy, dodając trzy reguły:

  • Znak minus w słowie w ogóle nie występuje albo występuje na początku słowa.
  • Pierwsza cyfra w słowie nie może być zerem, z wyjątkiem słowa „0”.
  • Każde słowo musi zawierać co najmniej jedną cyfrę.

  Ten zbiór opisuje zbiór liczb całkowitych i jest podzbiorem zbioru $\Sigma^\ast$ – jest więc językiem nad alfabetem $\Sigma$.

• Niech $\Sigma=\left\{0,1\right\}$. Domknięciem są więc wszystkie słowa złożone z zer i jedynek. Język L nad tym alfabetem możemy zdefiniować np. jako zbiór wszystkich słów, które mają dokładnie trzy jedynki. Możemy być też bardziej kreatywni i powiedzieć, że językiem L będzie zbiór wszystkich słów, które są poprawnym plikiem w formacie docx (to, co wychodzi z Worda).

• Zostańmy przy alfabecie binarnym $\Sigma=\left\{0,1\right\}$. Każdy łańcuch znaków (zwykłych znaków, które masz na klawiaturze) da się przekształcić do postaci binarnej, czyli do zer i jedynek, i z powrotem, na przykład za pomocą tablicy ASCII (a dokładniej – tablica ASCII zamienia znaki na liczby, a liczby z systemu dziesiętnego można zamienić na liczby w systemie dwójkowym). Możemy więc zdefiniować język wszystkich słów, które są poprawnym adresem e-mail, i nadal będzie to język nad alfabetem binarnym.

Konkatenacja języków: składać możemy także języki. Definicja będzie podobna jak przy iloczynie kartezjańskim zbiorów. Weźmy dwa języki L₁ i L₂. Przez ich konkatenację $L_1\circ L_2$ otrzymamy nowy język, który definiujemy tak:

$$ L_1\circ L_2 = \left\{w_1\circ w_2,|,w_1\in L_1, w_2\in L_2\right\} $$

Czyli bierzemy wszystkie słowa z języka L₁ i składamy je ze wszystkimi słowami z języka L₂. Przykład: niech

\begin{eqnarray} L_1&=&\left\{0,1\right\}\\ L_2&=&\left\{a,b,ahoj\right\}\\ \end{eqnarray}

Wtedy:

\begin{eqnarray} L_1\circ L_2 &=& \left\{0a, 0b, 0ahoj, 1a, 1b, 1ahoj\right\}\\ L_2\circ L_1 &=& \left\{a0, a1, b0, b1, ahoj0, ahoj1\right\}\\ L_1\circ L_1 &=& \left\{00, 01, 10, 11\right\} \end{eqnarray}

Do tej pory opisywaliśmy języki zwykłym językiem – po prostu słownie opisaliśmy, jak język ma wyglądać. To jednak bardzo niepraktyczne, dlatego wprowadza się bardziej formalne sposoby definiowania języka. Pierwszym z nich jest gramatyka.