Języki formalne

Język formalny jest pewnego rodzaju uogólnieniem pojęcia języka, do którego jesteśmy przyzwyczajeni w życiu codziennym.

Podstawowe pojęcia

Na początek możemy myśleć o języku formalnym jako o języku potocznym, takim jak angielski. Z czego składa się taki język? Składa się ze słów, które następnie łączymy w zdania. Nie interesują nas zdania, tylko słowa. Z czego składają się słowa? Z liter alfabetu. Zaczniemy od alfabetu.

Alfabet to dowolny niepusty zbiór. Elementy alfabetu nazywane są symbolami. Jeśli mówimy o języku czeskim, byłby to klasyczny czeski alfabet, zawierający zarówno małe, jak i wielkie litery, a także odmiany liter z haczykami i przecinkami. Gdybyśmy nie chcieli opisywać języka czeskiego, ale na przykład liczby, mielibyśmy wszystkie dziesięć cyfr w alfabecie. Alfabet często oznaczamy symbolem $\Sigma$.

Przez słowo lub ciąg znaków rozumiemy skończoną sekwencję symboli z 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 sekwencja "ahoj" lub "doberman", ale nie "večer" (nie mamy "č"), "Honza" (nie mamy "H") lub "dobry den" (nie mamy spacji). Przez długość słowa rozumiem liczbę symboli składających się na słowo.

Konkatenacja słów: jeśli mamy dwa słowa a = a₁a₂… a_n i b = b₁b₂… b_m, to konkatenacja słów da słowo ab = a₁a₂… a_nb₁b₂… b_m. Przykład: konkatenacja słów "hello" i "doberman" daje słowo "hello doberman". Konkatenację zaznaczamy kółkiem, np. $a\circ b$, lub nie zaznaczamy jej wcale i po prostu piszemy słowa po sobie bez specjalnego symbolu konkatenacji.

Puste słowo oznaczamy symbolem $\varepsilon$, aby oznaczyć słowo o długości zero. Jeśli połączymy słowo a = a₁… a_n z pustym słowem $\varepsilon$, otrzymamy słowo a. Czyli $a\circ\varepsilon=a$.

Domknięciem alfabetu $\Sigma$ jest zbiór wszystkich słów, które możemy utworzyć z alfabetu $\Sigma$, włącznie ze słowem pustym. Jego domknięcie oznaczamy przez $\Sigma^\ast$. Jeśli mamy alfabet binarny $\Sigma=\left\{0,1\right\}$, to

$$ \Sigma^\ast=\left\{\varepsilon,0{,}1,01{,}10,11{,}011,101{,}110,\dots\right\} $$

Czasami używamy również dodatniego domknięcia alfabetu, które jest ponownie wszystkimi słowami, które jesteśmy w stanie złożyć z alfabetu, z wyjątkiem słowa pustego. Pozytywne domknięcie oznaczamy przez $\Sigma^+$, a ważność to $\Sigma^+=\Sigma^\ast\setminus\left\{\varepsilon\right\}$.

Przykłady alfabetów

• Wróćmy do czeskiego przykładu. Każde czeskie słowo znajduje się w czapce alfabetu, który zawiera duże i małe litery oraz warianty akcentowane (plus być może myślnik "-"). Jeśli dodamy spację i znaki interpunkcyjne (przecinek, kropka, wykrzyknik, znak zapytania, ...) do tego alfabetu, otrzymamy wszystkie zdania, które możemy utworzyć w języku czeskim. Oczywiście, to zamknięcie będzie zawierać zdania takie jak "sadflsf kasdf kagrjewichiarzcáýker kf fkjbsjbgvbadfgsa!!!:??: ::::?:::sdf", ale są one nadal bardziej sensowne niż przemówienia Miloša Zemana.

• Jeśli nasz alfabet zawiera wszystkie cyfry $\Sigma=\left\{0, 1, \dots, 9\right\}$, to wszystkie liczby naturalne znajdą się w czapce - a nawet więcej. Będą też liczby zaczynające się od zera, np. 00054, lub samo zero, a także puste słowo, które oczywiście nie jest liczbą.

• 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, a dla każdego n∈ℕ₀ w domknięciu istnieje słowo, które ma n wykrzykniki i nie będzie żadnego innego słowa w domknięciu.

• Niech $\Sigma=\left\{qw,c\right\}$. Jest to bardzo dziwny alfabet, ponieważ zawiera słowo qw. Ten zapis nie jest zwykle używany, ponieważ jest mylący i dziwny, ale możemy go sobie wyobrazić, sklejając litery "q" i "w" tak, aby tworzyły jeden znak. Wtedy możemy zobaczyć słowo "qw" jako symbol "qw". Gdybyśmy utworzyli z tego symbolu słowo "qwcqw", to słowo to miałoby długość trzech - składałoby się z symboli "qw", "c" i "qw". Nie spotykamy się z takimi przypadkami alfabetu zbyt często, ale zdarzają się sytuacje, w których musimy użyć takich symboli składających się z wielu symboli.

Język formalny

Język(formalny) nad alfabetem $\Sigma$ jest dowolnym podzbiorem $\Sigma^\ast$. Tak więc, $L\subseteq\Sigma^\ast$ odnosi się do języka L nad alfabetem $\Sigma$. Przykłady języków:

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

• Możemy dodać znak minus "-" do poprzedniego zbioru cyfr, więc $\Sigma=\left\{0, 1, \dots, 9, -\right\}$. Zamknięciem są wszystkie słowa, które składają się z cyfr lub znaku minus. Oznacza to jednak, że słowa takie jak "12-84-", "1-5-8" lub "-" również należą do domknięcia. Język liczb całkowitych ℤ tworzymy poprzez dodanie trzech reguł:

  • Znak minus nie występuje w ogóle w słowie lub 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ę.

  Zbiór ten 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\}$ będzie domknięciem wszystkich słów składających się z zer i jedynek. Język L nad tym alfabetem można zdefiniować na przykład jako zbiór wszystkich słów, które mają dokładnie trzy jedynki. Możemy też być bardziej kreatywni i powiedzieć, że język L będzie zbiorem wszystkich słów, które reprezentują prawidłowy format pliku docx (to, co wychodzi z Worda).

• Pozostaniemy przy alfabecie binarnym $\Sigma=\left\{0,1\right\}$. Dowolny ciąg znaków (zwykłe znaki na klawiaturze) można przekonwertować na binarny, tj. zera i jedynki, i z powrotem, na przykład za pomocą tabeli ASCII (lub dokładniej, tabela ASCII konwertuje znaki na liczby, a liczby w systemie dziesiętnym można przekonwertować na liczby w systemie binarnym). Możemy więc zdefiniować język wszystkich słów, które pasują do ważnego e-maila i nadal będzie to język nad alfabetem binarnym.

Łączenie języków: możemy również łączyć alfabety. Definicja będzie podobna do iloczynu kartezjańskiego zbiorów. Miejmy dwa języki L₁ i L₂. Złączenie ich $L_1\circ L_2$ da nam nowy język, który zdefiniujemy następująco:

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

To znaczy, bierzemy wszystkie słowa z języka L₁ i konkatenujemy je ze wszystkimi słowami z języka L₂. Przykład.

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

Następnie:

\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 używaliśmy zwykłego języka do opisywania języków, po prostu opisując werbalnie, jak język powinien wyglądać. Jest to jednak bardzo niepraktyczne, więc wprowadzamy bardziej formalne sposoby definiowania języka. Pierwszym z nich jest gramatyka.