1.2. Языки и цепочки символов. Способы задания языков

1.2.1. Общие представления о языках

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

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

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

– соответствия между последовательностями знаков и смыслами, делающего «осмысленными» допустимые последовательности знаков.

Знаками могут быть буквы алфавита, в том числе математические обозначения, а также звуки, жесты и т. п.

Вопрос слушателям. Можете ли вы привести примеры языков, на основе звуков, жестов, запахов?

Математическая лингвистика рассматривает только такие знаковые системы, в которых знаками являются символы некоторого алфавита, а последовательностями знаков – тексты, т. е. языки рассматриваются как произвольные последовательности осмысленных текстов. При этом правила, определяющие множество текстов, образуют синтаксис языка, а описание множества символов и соответствия между смыслами и текстами – семантику языка.

Семантика языка зависит от характера объектов, описываемых языком, и средства ее изучения различны для различных типов языков. Синтаксис же языка в меньшей степени зависит от назначения языка и может изучаться методами, не зависящими от содержания и назначения языка. Математический аппарат для изучения синтаксиса языков получил название Теория Формальных Грамматик (ТФГ). С точки зрения синтаксиса язык понимается уже не как средство общения, а как множество формальных объектов – последовательностей символов алфавита, при этом какие-то содержательные интерпретации объектов отсутствуют.

Основными терминами ТФГ являются: символ – как простой неделимый знак и цепочка символов. Множество символов образуют алфавит.

1.2.2. Цепочки символов. Операции над цепочками символов

Цепочкой символов (или строкой) называется произвольная, упорядоченная, конечная последовательность символов, записанных один за другим.

Для обозначения цепочек обычно используют символы (буквы) греческого алфавита: , ,  и т. д.

Цепочка символов – это последовательность, в которую входят любые допустимые символы. Последовательность символов может быть как осмысленной, так и неосмысленной. Например, предложение в книге – это осмысленная цепочка, а последовательность «аааааа…грьь, -лл» - неосмысленная цепочка. Эти примеры подтверждают свойство произвольности.

Цепочка символов – это упорядоченная последовательность символов. Это значит, что для цепочки имеют значения три фактора: состав входящих в цепочку символов; их количество; порядок символов в цепочке. Поэтому цепочки «а» и «аа», «аб» и «ба» – это все различные цепочки. Две цепочки  и  равны (совпадают)  = , если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке. То есть каждая цепочка может быть представлена как кортеж.

Количество символов в цепочке называют длиной цепочки, и она обозначается так же как мощность множества, например, для цепочки  длина равна . Если  = , то  = .

Основной операцией над цепочками является операция конкатенации (объединение или сложение) цепочек.

Конкатенация двух цепочек – это дописывание второй цепочки в конец первой. Конкатенация цепочек  и  обозначается как . Конкатенация – это достаточно простое действие, т. е. если  = аб, а  = бв, то  = аббв. Надо иметь ввиду, что конкатенация цепочек не обладает свойством коммутативности, т. е. в общем случае а  а. Но возможно для некоторых цепочек выполнение условия  = .

Например,  = аааа,  = а, что можно сказать о  и ?

Придумайте пример, когда   ,   ,   , а  =  = .

Конкатенация обладает свойством ассоциативности, т. е. () = (). Например,  = а,  = б,  = в, то () = абв, и () = абв.

Любую цепочку символов языка можно многовариантно представить как конкатенацию составляющих ее частей, если разбить цепочку на несколько подцепочек. Например, цепочку  = абвг можно представить как  = , где  = аб, а  = вг, или  = , где  = а,  = бвг.

Чем длиннее исходная цепочка, тем больше вариантов разбиения ее на подцепочки.

Если некоторую цепочку разбить на соответствующие подцепочки, а затем заменить одну из подцепочек на любую произвольную цепочку символов, то получится новая цепочка символов, а само такое действие называется заменой или подстановкой цепочки.

Например,  = абвг,  = а,  = б,  = вг, т. е.  = .

Вместо подцепочки  сделаем подстановку цепочки  = аба.

В результате получим новую цепочку ^ = аабавг(^ = ).

Любая подстановка выполняется с помощью разбиения исходной цепочки на подцепочки и операции конкатенации.

Еще одной операций над цепочкой является операция обращения цепочки, соответствующая записи символов цепочки в обратном порядке. Обозначается эта операция следующим образом: для цепочки  обращенная цепочка ^R. Если  = абвг, то ^R = гвба. Но если  = , где  = аб,  = вг, тогда ()^R = ^R^R, т. е. для операции обращения справедливо:

_,[()^R = ^R^R],

т. е. обращение конкатенации двух цепочек равно обращенной конкатенации обращений этих цепочек.

Вопрос слушателям. Как показать справедливость этого выражения на примерах? Каков будет результат, если рассмотреть обращение конкатенации трех цепочек?

Операция многократной конкатенации цепочки самой с собой называется итерацией (повторением). Итерация цепочки  n раз обозначается как ⁿ. Для итерации справедливы следующие выражения при n  0:

_: ¹ = , ² = , ³ =  и т. д.

При n = 0 результатом итерации будет пустая цепочка символов.

Пустая цепочка символов – это цепочка, не содержащая ни одного символа. Для идентификации пустой цепочки используется буква .

Для пустой цепочки справедливы следующие равенства:

1)  = 0;

2) _( =  = );

3) ^R = ;

4) _{n  0}(ⁿ = );

5) _(⁰ = ).