Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

Формальна породжувальна граматика G - це формальна система, обумовлена четвіркою об'єктів G = < V, W, I, P >, де V - алфавіт термінальних символів; W - алфавіт нетермінальних символів (V Ç W = Æ); I - початковий символ (аксіома) граматики; P - кінцева множина правил вигляду , де і - ланцюжки в алфавіті V È W. Ланцюжок безпосередньо виведений із ланцюжка в граматиці G (позначається a Þ_G b). Індекс G опускається, якщо ясно, про яку граматику йде мова.

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

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

У теорії грамматик склалися свої традиції позначень, яких ми будемо дотримуватися. Символи термінального алфавіту прийнято позначати малими латинськими буквами, ланцюжки в алфавіті V È W - грецькими буквами. Довжина ланцюжка a позначається l (a) або çaç, множина всіх ланцюжків у алфавіті - 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' - множина всіх правил виводу А ® a (аÎV, A - двійник а), а R" отримано з R заміною в кожному правилі усіх входжень термінальних символів входженнями їхніх двійників. Кожному виводу І, e₁,... e_n у G відповідає висновок І, e₁... e_n, e_n+1,..., e_n+m у G', де e'_i (і ≤ n) отримано з e' заміною всіх символів із V їхніми двійниками, а e_n+J(j ≤ m) отримано з e_n+J-1 застосуванням правила з R^', причому до e'_n+m правила з R^' уже не застосовні. Ясно, що e'_n+m = e_n, тому L(G) Í L(G₁). Оскільки тільки правила з R^' містять термінальні символи в правих частинах, то будь-який висновок із G₁ ланцюжка довжини m повинне містити m застосувань правил із R^'. Видаливши з виведення застосування цих правил і привівши в ньому обернене перейменування двійників у символи V, одержимо виведення цього ж ланцюжка в G. Звідси

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

L(G) = L(G₁).

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

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

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

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

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

a A b ® a ω b, де ω Î (VÈW)⁺.

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

Граматика типу 2, або контекстно-вільна граматика (КВ-граматика) - це граматика, усі правила якої мають вигляд A ® a, де aÎ(VÈW)*.

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

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