4.5. Мови і граматики

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

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

а) знакової системи, тобто множини припустимих послідовностей знаків;

б) множини змістів цієї системи;

в) відповідності між послідовностями знаків і змістами, що робить "осмисленими" припустимі послідовності знаків.

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

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

Саме інтерес до мов програмування і необхідність вирішення завдання машинного перекладу природних мов призвели до виникнення нової науки - математичної лінгвістики, що розглядає мови як довільну множину осмислених текстів.

Правила, що визначають множину текстів, утворюють синтаксис мови; опис множини змістів і відповідності між текстами і змістами - семантику мови. Семантика мови залежить від характеру об'єктів, що описуються мовою, і засоби її вивчення для різноманітних типів мов різноманітні. Використання і дослідження семантики мов програмування стала самостійною галуззю теоретичного програмування.

Розвиток семантики пов'язаний, насамперед, із машинним перекладом.

Що ж стосується синтаксису, то його особливості набагато менше залежать від призначення і цілей мови. Саме у вивченні синтаксису отримані значні результати, і за останні 30 років склався спеціальний математичний апарат - теорія формальних граматик. При цьому мова розглядається не як засіб спілкування, а як множина формальних об'єктів - послідовностей символів алфавіту. Далі такі послідовності будуть називатися словами.

4.6. Формальні грамматики і їхні властивості

Нехай заданий алфавіт V і тим самим множина V^* усіх кінцевих слів або ланцюжків в алфавіті V. Формальна мова L в алфавіті V - це довільна підмножина L  V^. Конструктивний опис формальних мов здійснюється за допомогою формальних систем спеціального вигляду, які називаються формальними породжувальними граматики.

Формальна породжувальна граматика G - це формальна система, обумовлена четвіркою об'єктів G =  V, W, I, P , де V - алфавіт термінальних символів; W - алфавіт нетермінальних символів (V  W = ); I - початковий символ (аксіома) граматики; P - кінцева множина правил вигляду , де і - ланцюжки в алфавіті V  W. Ланцюжок безпосередньо виведений із ланцюжка в граматиці G (позначається  _G ). Індекс G опускається, якщо ясно, про яку граматику йде мова.

Якщо = , = і , то правило виведення в граматиці G формулюється таким чином: ланцюжок може бути виведений із , якщо існує послідовність ₀= , Е₁, Е₂, ... Е_n= , така, що для всіх і=0, 1, …, -1 _i  _i+1. Ця послідовність називається висновком із , а n - довжиною виведення. Вивідність із позначається .

Мовою L(G), породжуваною граматикою G, називається множина всіх ланцюжків у термінальному алфавіті V, виведених з І. Граматики G і G' еквівалентні, якщо L(G)=L(G').

У теорії грамматик склалися свої традиції позначень, яких ми будемо дотримуватися. Символи термінального алфавіту прийнято позначати малими латинськими буквами, ланцюжки в алфавіті V  W - грецькими буквами. Довжина ланцюжка  позначається l() або , множина всіх ланцюжків у алфавіті - V  V^. Множина всіх непустих ланцюжків позначається V^.

Лема 1. Для довільної граматики G існує еквівалентна їй граматика G1, ліві частини правил якої не містять входжень основних символів.

Нехай G = V, W, R, I. Кожному символу а V поставимо у відповідність двійник - символ А, що не утримується в VW; множину всіх двійників позначимо V'.

Визначимо тепер G₁=V₁, W₁, R₁, I₁ у такий спосіб: V₁=V, I₁=I, W₁= WV', a R₁ = R'  R", де R' - множина всіх правил виводу А   (аV, A - двійник а), а R" отримано з R заміною в кожному правилі усіх входжень термінальних символів входженнями їхніх двійників. Кожному виводу І, ₁, ... _n у G відповідає висновок І, ₁... _n, _n+1, ... , _n+m у G', де '_i (і ≤ n) отримано з ' заміною всіх символів із V їхніми двійниками, а _n+J(j ≤ m) отримано з _n+J-1 застосуванням правила з R^', причому до '_n+m правила з R^' уже не застосовні. Ясно, що '_n+m = _n, тому L(G)  L(G₁). Оскільки тільки правила з R^' містять термінальні символи в правих частинах, то будь-який висновок із G₁ ланцюжка довжини m повинне містити m застосувань правил із R^'. Видаливши з виведення застосування цих правил і привівши в ньому обернене перейменування двійників у символи V, одержимо виведення цього ж ланцюжка в G. Звідси

L(G₁)  L(G) і, отже,

L(G)  L(G₁).

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

Таким чином, формальні граматики спроможні породжувати будь-які зчисленні множини.

Специфіка формально-лінгвістичного підходу до опису множин ланцюжків починає виявлятися при розгляді більш вузьких класів граматик. Узвичаєною класифікацією граматик і породжуваних ними мов є ієрархія Хомського, що містить чотири типи граматик.

Граматика типу 0 - це граматика довільного типу без обмежень на правила висновка.

Граматика типу 1 (контекстна граматика) - це граматика, усі правила якої мають вигляд

     ω , де ω  (VW)⁺.

Ланцюжки  і  - це контекст правила. Вони не змінюються при його застосуванні.

Граматика типу 2, або контекстно-вільна граматика (КВ-граматика) - це граматика, усі правила якої мають вигляд   , де VW)* .

Граматика типу 3, або регулярна граматика - це грамматика, усі правила якої мають вигляд або A  , або   .

Мова L називається мовою типу і (і=0, 1, 2, 3), якщо існує граматика типу і, що її породжує.