12. Формальні граматики

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

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

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

Як приклад такого правила приведемо (у нотації Бекуса) визначення ідентифікатора для мови програмуван­ня:

<ідентифікатор>::=<літера> | <ідентифікаторхлітера> | <ідентифікаторхцифра>

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

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

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

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

13. Теорія алгоритмів

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

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

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

1. Алгоритм має справу з даними - вихідними, проміжними й вихідними, записаними в деякому алфавіті, і за­ стосовується до різних наборів даних.

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

3. Послідовність кроків детермінована.

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

Алгоритмічні мови – лише засоби для запису алгоритмів. Для фактичного виконання останніх потрібно де­яка інтерпретуюча система.

Відомо кілька десятків універсальних алгоритмічних моделей, які в остаточному підсумку виявилися еквіва­лентними. Частіше інших використовуються

1. Рекурсивні функції,

2. Машини Т'юрінга,

3. Продукційна система Поста,

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

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

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