Формальные грамматики и их свойства

Раздел 5. Языки и грамматики

Вступление

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

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

Знаковой системы , т. е. множества допустимых последовательностей знаков;

Множества смыслов этой системы;

3) Соответствия между последовательностями знаков и смыслами, делающими "осмысленными" допустимые последовательности знаков.

Знаками могут быть буквы алфавита, математические обозначения и т. д. Наука об осмысленных знаковых системах называется семиотикой.

Семиотический подход оказался весьма плодотворным в различных областях знаний - в биологии, социологии, лингвистике.

При этом разные ветви семиотики имеют значительную специфику и не везде еше используют точные математические средства. Наиболее продвинутыми являются исследования знаковых систем, в которых знаками являются символы алфавитов, а последовательности знаков - тексты. К таким знаковым системам относятся естественные языки, языки науки, а также языки программирования.

Именно интерес к языкам программирования и необходимость решения задачи машинного перевода естественных языков привели к возникновению новой науки - математической лингвистики, которая рассматривает языки как произвольное множество осмысленных текстов.

Правила, определяющие множества текстов, образует синтаксис языка; описание множества смыслов и соответствия между текстами и смыслами - семантику языка. Семантика языка зависит от характера объектов, которые описываются языком и средства ее изучения для различных типов языков различны.

О семантике языка метаматематики - формальных теориях - речь шла в четвертом разделе. Использование и исследование семантики языков программирования стало самостоятельной отраслью теоретического программирования. Развитие семантики связано прежде всего с машинным переводом.

Что же касается синтаксиса, то его особенности гораздо меньше зависят от назначения и целей языка. Именно в изучении синтаксиса получены значительные результаты и за последние 30 лет здесь сложился специальный математический аппарат - теория формальных грамматик. При этом язык рассматриваются не как средство общения, а как множество формальных объектов - последовательностей символов алфавитов. Далее такие последовательности будут называться словами.

Формальные грамматики и их свойства

Пусть задан алфавит V и тем самым множество V^* всех конечных слов или цепочек в алфавите V. Формальный язык L в алфавите V - это произвольное подмножество L Í V^*. Конструктивное описание формальных языков осуществляется с помощью формальных систем специального вида, называемых формальными порождающими грамматиками.

Формальная порождающая грамматика G - это формальная система, определяемая четверкой объектов G = {V, W, I, P}, где V - алфавит терминальных символов; W - алфавит нетерминальных символов (V Ç W = Æ); I - начальный символ (аксиома ) грамматики; Р - конечное множество правил вида x ® h, где x, h- цепочки в алфавите V ÈW. Цепочка b непосредственно выводима из цепочки a в грамматике G (обозначается a Þ b). Индекс G опускается, если ясно, о какой грамматике идет речь.

G

Если a = g x d, b = g h d и x ® h то это правило в грамматике G.

Цепочка b выводима из a если существует последовательность a = e₀; e₀ = e₁, ... .

e_n = b, такая, что для всех i = 0, 1, ... , n - 1 справедливо e_i ® e_i+1. Эта последовательность называется выводом b из a, а n - длинной вывода. выводимость b из a обозначается a ® b.

n

Языком L(G) порождаемым грамматикой G называется множество всех цепочек в терминальном алфавите V, выводимых из I. Грамматика G и G^' эквивалентны, если L(G) = L(G^').

В теории грамматик сложились свои традиции обозначений, которых мы будем придерживаться. Символы терминального алфавита принято обозначать малыми латинскими буквами, цепочки в алфавите V È W - греческими буквами. Длинна цепочки a обозначается l(a) или ça ç. Множество всех цепочек в алфавите V ® V^*.

Множество всех непустых цепочек обозначается V⁺.

Лемма 1. Для произвольной грамматики G существует эквивалентная ей грамматика G₁, левые части правил которой не содержат вхождений основных символов. Пусть G = {V, W, R, I}. Каждому символу а Î V поставим в соответствие двойник - символ А, не содержащийся в V È W; множество всех двойников обозначим V^'.

Определим теперь G₁ = {V₁, W₁, R₁, I₁} следующим образом: V₁ = V; I₁ = I; W₁ = W

È V^', а R₁ = R^' È R^", где R^' - множество всех правил вида А ® а (а Î V, А - двойник а), а R^" получено из R заменой в каждом правиле всех вхождений терминальных символов вхождениями их двойников. Каждому выводу I, e₁, ... , e_n в G соответствует вывод I, e₁^',

... , e_n^', e_n+1^', ... , e_n+m^' в G^', где e_i^' ( 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 - множество ее заключительных слов.