Формальні мови

Формальна мова — це певне узагальнення поняття мови, до якого ми звикли в повсякденному житті.

Основні поняття

Для початку формальну мову можна уявляти як звичайну мову, наприклад українську. З чого складається така мова? Зі слів, які ми далі поєднуємо в речення. Речення нас не цікавитимуть, нас цікавитимуть лише слова. З чого складаються слова? З літер алфавіту. Тож почнімо з алфавіту.

Алфавіт — це довільна непорожня множина. Елементи алфавіту називаємо символами. Якщо йдеться про українську мову, це буде звичайний український алфавіт, що містить малі й великі літери, а також апостроф. Якби ми хотіли описувати не українську мову, а, наприклад, числа, то в алфавіті було б усіх десять цифр. Алфавіт часто позначають символом $\Sigma$.

Словом, або також рядком, називаємо скінченну послідовність символів із деякого алфавіту $\Sigma$. Якщо маємо, наприклад, алфавіт $\Sigma=\left\{a,b,c,d,e,\dots, z\right\}$, то словом є послідовність «hello» або «world», але вже не «Kyiv» (немає великої літери «K»), не «Київ» (немає кириличних літер) і не «hello world» (немає пропуску). Довжиною слова називаємо кількість символів, з яких воно складається.

Конкатенація слів: якщо маємо два слова a = a₁a₂… a_n і b = b₁b₂… b_m, то конкатенацією слів утвориться слово ab = a₁a₂… a_nb₁b₂… b_m. Приклад: конкатенацією слів «hello» і «world» утвориться слово «helloworld». Конкатенацію позначають або кружечком, тобто $a\circ b$, або ніяк не позначають і просто записують слова одне за одним без спеціального символу.

Порожнє слово позначаємо $\varepsilon$; це слово, що має довжину нуль. Якщо виконати конкатенацію слова a = a₁… a_n з порожнім словом $\varepsilon$, отримаємо назад слово a. Тобто виконується $a\circ\varepsilon=a$.

Замикання алфавіту $\Sigma$ — це множина всіх слів, які ми можемо утворити з алфавіту $\Sigma$, разом із порожнім словом. Замикання позначаємо $\Sigma^\ast$. Для двійкового алфавіту $\Sigma=\left\{0,1\right\}$ маємо

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

Іноді використовують ще додатне замикання алфавіту — це знову всі слова, які можна скласти з алфавіту, крім порожнього слова. Додатне замикання позначаємо $\Sigma^+$, і виконується $\Sigma^+=\Sigma^\ast\setminus\left\{\varepsilon\right\}$.

Приклади алфавітів

• Повернімося до прикладу з українською мовою. Кожне українське слово можна знайти в замиканні алфавіту, який містить малі й великі літери (можливо, ще дефіс «-» та апостроф). Якщо до цього алфавіту додати ще пропуск і розділові знаки (кому, крапку, знак оклику, знак питання, …), то замиканням отримаємо всі речення, які ми можемо скласти українською. Звісно, до цього замикання належатимуть і «речення» на кшталт «фвапр олдж ячсмїєґщзх'ш кф ффіварпо!!!:??: ::!?:?:длж», які, утім, усе одно осмисленіші за деякі коментарі в інтернеті.

• Якщо наш алфавіт містить усі цифри $\Sigma=\left\{0, 1, \dots, 9\right\}$, то в замиканні будуть усі натуральні числа — і ще дещо зайве. Там будуть також числа, що починаються з нуля, наприклад 00054, або сам нуль, а крім того, порожнє слово, яке, звісно, жодним числом не є.

• Алфавіт має бути непорожнім, тож найменший алфавіт має принаймні один символ. Наприклад, для алфавіту $\Sigma=\left\{!\right\}$ отримаємо замикання $\Sigma^\ast=\left\{\varepsilon, !, !!, !!!, !!!!, \dots\right\}$, тобто множину слів, причому для кожного n∈ℕ₀ у замиканні існує слово, що має n знаків оклику, і жодних інших слів там не буде.

• Нехай $\Sigma=\left\{qw,c\right\}$. Це дуже дивний алфавіт, адже він містить слово qw. Такий запис зазвичай не використовують, бо він заплутаний і дивний, але можна уявити, що ми «склеюємо» літери «q» і «w» так, що вони утворюють один знак. Тоді слово «qw» можна розглядати як символ «qw». Якби ми склали з цього символу слово «qwcqw», то його довжина дорівнювала б трьом — воно складалося б із символів «qw», «c» і «qw». Із подібними алфавітами ми зустрічаємося нечасто, але бувають ситуації, коли потрібні такі символи, що складаються з кількох символів.

Формальна мова

(Формальна) мова над алфавітом $\Sigma$ — це довільна підмножина множини $\Sigma^\ast$. Отже, для мови L над алфавітом $\Sigma$ виконується $L\subseteq\Sigma^\ast$. Приклади мов:

• У попередній частині ми означили алфавіт цифр $\Sigma=\left\{0, 1, \dots, 9\right\}$. Замиканням є всі слова, що складаються лише з цифр. Якщо додати правило, що слово не може починатися з нуля і не може бути порожнім, отримаємо множину натуральних чисел ℕ. Виконується співвідношення $\mathbb{N}\subseteq\Sigma^\ast$, тож ℕ є мовою над алфавітом $\Sigma$.

• До попередньої множини цифр можна додати ще знак мінус «-», тож $\Sigma=\left\{0, 1, \dots, 9, -\right\}$. Замиканням є всі слова, що складаються з цифр або знака мінус. Це, однак, означає, що в замиканні є й такі слова, як «12-84-», «1-5-8» або «-». Мову цілих чисел ℤ утворимо, додавши три правила:

  • Знак мінус у слові або не трапляється взагалі, або стоїть на початку слова.
  • Перша цифра слова не може бути нулем, окрім слова «0».
  • Кожне слово має містити принаймні одну цифру.

  Ця множина описує множину цілих чисел і є підмножиною множини $\Sigma^\ast$ — отже, це мова над алфавітом $\Sigma$.

• Нехай $\Sigma=\left\{0,1\right\}$. Замиканням є всі слова, що складаються з нулів та одиниць. Мову L над цим алфавітом можна означити, наприклад, як множину всіх слів, що мають рівно три одиниці. Можна навіть пофантазувати й сказати, що мова L — це множина всіх слів, які є коректним форматом файлу docx (того, що виходить із Word).

• Залишимося при двійковому алфавіті $\Sigma=\left\{0,1\right\}$. Кожен рядок символів (звичайних знаків, які є на клавіатурі) можна перетворити на двійковий вигляд, тобто на нулі й одиниці, і назад, наприклад за допомогою таблиці ASCII (точніше, таблиця ASCII перетворює знаки на числа, а числа з десяткової системи можна перевести в двійкову). Тож ми можемо означити мову всіх слів, що відповідають коректній електронній адресі, і це й далі буде мова над двійковим алфавітом.

Конкатенація мов: конкатенацію можна виконувати й для мов. Означення буде подібне до декартового добутку множин. Нехай маємо дві мови L₁ і L₂. Їхньою конкатенацією $L_1\circ L_2$ отримаємо нову мову, яку означаємо так:

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

Тобто беремо всі слова з мови L₁ і виконуємо конкатенацію кожного з усіма словами з мови L₂. Приклад: нехай

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

Тоді виконується:

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

Досі для опису мов ми користувалися звичайною мовою, тобто просто словами описували, як має виглядати мова. Це дуже незручно, тому вводять формальніший спосіб означення мови. Перший із них — граматика.