Формальні граматики. Теорія алгоритмів

Виникнення метаматематики (що пов’язано з роботами з обґрунтування математики) та її розвиток, структурні дослідження у лінгвістиці, в особливості роботи з машинного перекладу (наприклад, з алгоритмічних мов – на машинну) спричинили створення науки про обґрунтовані знакові системи.

Формальні мови – це множина формальних ланцюгів символів алфавіту, що породжуються граматикою мови, яка визначається як четвірка об’єктів G=<T,U,A,P>, де Т – множина термінальних (алфавітних) символів; U – множина не термінальних символів, які утворюють ієрархічну систему довільних понять мови; А – найзагальніше поняття, яке називається аксіомою (у випадку алгоритмічних мов – програма в цілому); Р – сукупність правил виведення. Прикладом такого правила є означення ідентифікатора для мов програмування:

<ідентифікатор>: : = <буква> |<ідентифікатор><буква>

|<ідентифікатор><цифра>

(послідовність букв та цифр, яка починається з букви).

Зв’язок мови з граматикою, що його породжує, має ту ж природу, що й зв’язок функції з алгоритмом її обчислення. Проблема визначення властивостей мови за його граматикою у загальному випадку не може бути розв’язаною.

Практичне застосування теорії формальних граматик (ТФГ) пов’язані переважно з аналізом вхідного ланцюга символів, із збіркою з нього понять, що класифікують. Зокрема, важливим є застосування ТФГ для системи ШІ: за його допомогою розв’язують задачі з технічної діагностики і аналізу телеметричної інформації. Складність цих задач залежить від класу граматики, який визначається типом правил, що породжує (зокрема, їх залежністю від контексту для ланцюгів символів). Найпростіші граматики відповідають скінченним автоматам. Методи ТФГ застосовуються також і при розробці людино-машинного інтерфейсу системи ШІ.

Трансформаційні граматики, що інтенсивно розробляються останнім часом, дають змогу враховувати семантику предметної галузі. Фраза мови (ланцюг символів) має семантику, якщо система може перетворювати цей ланцюг у деяке значення. Сенс ланцюга визначається через ознаки кожного нетермінального символу, який виникає при граматичному опрацюванні цього ланцюга відповідно до правил граматики. Ці ознаки поділяються на унімодальні від більш загальних конструкцій та синтезовані – від тих, що включаються. Вибір правил можна зробити залежним від поточного стану предметної галузі.

Алгоритмом прийнято називати будь-яку скінченну систему правил перетворення інформації над скінченним алфавітом. Букви алфавіту є первинним типом елементарних даних, слова, що з них складаються, можуть розглядатися як одновимірні масиви. З букв та слів формуються нові (структуровані) типи даних, над якими здійснюються специфічні операції. За допомогою операцій будуються формули мови – вирази. Оператори мови здійснюють перетворення даних і можуть містити посилання на оператор, який виконується наступним оператором. Програма, з формальної точки зору, представляє собою скінченну впорядковану послідовність операторів.

Теорія алгоритмів з’ясовує, які об’єкти та дії над ними слід вважати точно визначеними; які властивості і можливості мають комбінації елементарних дій; що можна і що не слід робити з їх допомогою. Головним внутріматематичним застосуванням теорії алгоритмів є доведення неможливості алгоритмічного розв’язання деяких математичних проблем. Такі доведення (і навіть точні формулювання тверджень, що доводяться) нездійсненні без строгого поняття алгоритму.

Основні вимоги до алгоритмів:

1) алгоритм має справу з даними: вихідними, проміжними та кінцевими, записаними у певному алфавіті; він може бути застосований до різних наборів даних;

2) алгоритм складається з окремих елементарних кроків, спосіб виконання яких відомий системі;

3) послідовність кроків є детерміновою;

4) алгоритм закінчується після скінченого числа кроків.

Алгоритмічні мови – це лише засоби для запису алгоритмів, для фактичного виконання яких потрібна певна система, що інтерпретує. Відомі кілька десятків алгоритмічних моделей, які в кінцевому підсумку виявилися еквівалентними. Частіше за інші використовуються такі:

1) рекурсивні функції;

2) машини Тюрінга;

3) продукційна система Поста;

4) нормальні алгоритми Маркова.

Доведено, що жодна нетривіальна властивість обчислюваних функцій не є алгоритмічно розв’язуваною. Сутність цього полягає в тому, що по опису алгоритму в загальному випадку нічого не можна дізнатися про властивості обчислюваної функції. Зокрема, нерозв’язуваною є проблема упізнавання еквівалентності алгоритмів за їх описами.

Знання основних нерозв’язуваностей за логікою та її додатками для фахівця, є такою ж мірою істотним, як для інженера питання про неможливості побудови вічного двигуна. Нерозв’язуваність зазвичай є наслідком надмірно загальної постановки питання.