✖

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

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

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

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

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

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

Конкатенація слів: якщо маємо два слова a = a1a2… an і b = b1b2… bm, то конкатенацією слів утвориться слово ab = a1a2… anb1b2… bm. Приклад: конкатенацією слів «hello» і «world» утвориться слово «helloworld». Конкатенацію позначають або кружечком, тобто a ∘ b, або ніяк не позначають і просто записують слова одне за одним без спеціального символу.

Порожнє слово позначаємо ε; це слово, що має довжину нуль. Якщо виконати конкатенацію слова a = a1… an з порожнім словом ε, отримаємо назад слово a. Тобто виконується a ∘ ε = a.

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

Σ∗={ε,0,1,00,01,10,11,000,001,…}

Іноді використовують ще додатне замикання алфавіту — це знову всі слова, які можна скласти з алфавіту, крім порожнього слова. Додатне замикання позначаємо Σ+, і виконується Σ+ = Σ∗ ∖ {ε}.

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

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

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

  • Алфавіт має бути непорожнім, тож найменший алфавіт має принаймні один символ. Наприклад, для алфавіту Σ= {!} отримаємо замикання Σ∗ = {ε, !, !!, !!!, !!!!, …}, тобто множину слів, причому для кожного n ∈ ℕ0 у замиканні існує слово, що має n знаків оклику, і жодних інших слів там не буде.

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

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

(Формальна) мова над алфавітом Σ — це довільна підмножина множини Σ∗. Отже, для мови L над алфавітом Σ виконується L ⊆ Σ∗. Приклади мов:

  • У попередній частині ми означили алфавіт цифр Σ= {0, 1, …, 9}. Замиканням є всі слова, що складаються лише з цифр. Якщо додати правило, що слово не може починатися з нуля і не може бути порожнім, отримаємо множину натуральних чисел ℕ. Виконується співвідношення ℕ ⊆ Σ∗, тож ℕ є мовою над алфавітом Σ.

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

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

    Ця множина описує множину цілих чисел і є підмножиною множини Σ∗ — отже, це мова над алфавітом Σ.

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

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

Конкатенація мов: конкатенацію можна виконувати й для мов. Означення буде подібне до декартового добутку множин. Нехай маємо дві мови L1 і L2. Їхньою конкатенацією L1 ∘ L2 отримаємо нову мову, яку означаємо так:

L1∘L2={w1∘w2|w1∈L1,w2∈L2}

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

L1={0,1}L2={a,b,hello}

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

L1∘L2={0a,0b,0hello,1a,1b,1hello}L2∘L1={a0,a1,b0,b1,hello0,hello1}L1∘L1={00,01,10,11}

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