Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Часть /. Предварительные сведения из логики и алгебры
А, а затем — непосредственно за ними — все вхождения из В. Мы будем говорить, что С получается конкатенацией А и В, и писать
С = AB.
Пример. Для А = 'Ьаса' и B = 'ас' мы имеем AB = 'Ьасаас' и BA = 'acbaca'.
Цепочка, полученная в результате конкатенации, имеет длину, равную сумме длин образующих ее цепочек.
Ясно, что конкатенация является всюду определенной и ассоциативной, но не коммутативной операцией; заметим, что для конкатенации существует единичный элемент, а именно пустая цепочка.
Множество, снабженное всюду определенной ассоциативной операцией, называется в алгебре полугруппой. Снабдив множество її* операцией конкатенации, мы превращаем его в свободную полугруппу над 91, причем элементы її являются образующими этой полугруппы.
Примеры. Если її = {а}, то свободная полугруппа изоморфна множеству степеней одной буквы а (с ассоциативным умножением) .
Если її = {0, 1}, то цепочки множества 91* можно трактовать как целые двоичные числа; тогда конкатенацию можно интерпретировать как некоторую довольно сложную арифметическую операцию.
1.1.4. Вопросы терминологии
В теории формальных грамматик терминология еще окончательно не установилась. Она колеблется в зависимости от авторов и от областей применения этой теории (искусственные языки, логика, естественные языки и т. д.).
Имея в виду исследование языков программирования, мы будем называть базу абстрактным алфавитом, состоящим из абстрактных букв, и говорить, что он представляется в данных условиях конкретным алфавитом, состоящим из конкретных букв. Цепочки в абстрактном алфавите мы будем называть абстрактными словами-, абстрактные слова представляются конкретными словами ').
') Таким образом, термин слово означает то же самое, что цепочка. В оригинале соответствующее понятие также обозначается в разных местах разными терминами {mot, phrase, иногда sequence) Такое словоупотребление связано со следующим обстоятельством. В алгебре и теории алгоритмов для обозначения конечных последовательностей символов (букв) уже довольно давно используется термин слово (нем Wort, англ. word, фр. mot) Однако в работах по математической лингвистике этого термина избегают, чтобы не создавать омонимии при лингвистической интерпретации, в которой слова естественного яяыка обычно соответствуют элементарным символам (буквам), а «словам» формальных Гл. I. Слова (цепочки). Полугруппы. Языки
17
Так, в языке программирования Алгол-60 используется алфавит из 116 букв. Абстрактная буква определяется здесь множеством характеризующих ее свойств: например, абстрактная буква, которая играет роль начальной скобки перед набором команд, записывается с помощью конкретной буквы «begin»1); другая абстрактная буква, соответствующая логической импликации, записывается с помощью конкретной буквы «=Э» 2). Не следует смешивать саму импликацию со значком =>3). Подчеркнем, что для записи алгольных программ на перфоленту используется другой конкретный алфавит, а для записи соответствующей информации в машине — третий.
В естественных языках базу можно считать состоящей из букв или фонем, последовательности которых являются словами. Можно также рассматривать в качестве базы словарь, элементы которого суть слова (в обычном лингвистическом смысле); последовательности слов — это словосочетания, предложения и т. п. Здесь
языков отвечают словосочетания и предложения. Поэтому в работах по теории порождающих грамматик на английском языке вместо word обычно используется термин string, на русском языке — цепочка. В настоящем переводе также используется этот последний термин, но в разделах, относящихся к алгебре и теории алгоритмов, сохранен термин слов о, так как в этом контексте термин цепочка звучал бы слишком непривычно — Прим. ред.
') Буква «begin» принадлежит к международному алфавиту Алгола, описанному в официальном сообщении «Алгол-60» В СССР в этом же значении используется конкретная буква «начало».
О языке Алгол-60 см., в частности, «Алгоритмический язык Алгол-60 (пересмотренное сообщение)», изд-во «Мир», M., 1965. После выхода в свет этой книги появился новый вариант Алгола — Алгол-68, см официальное описание в журнале Кибернетика (Киев), № 6 (1969) и № 1 (1970). — Прим перев.
2) Авторы, по-видимому, считают, что во всех случаях, когда для обозначения импликации используется значок в форме подковы, обращенной закруглением вправо (а не, скажем, стрелка), или в качестве левой скобки перед набором команд — напечатанное полужирным шрифтом английское слово begin (а не русское слово начало, не какой-либо цифровой код, не курсивное begin и т. п), можно говорить об одной и той же конкретной букве Такая трактовка представляется не вполне удачной. Понятие «значок =>» — это уже результат абстракции отождествления; при образовании этого понятия нам приходится отвлечься, в частности, от многочисленных графических особенностей конкретных значков данного вида Еще более это очевидно в отношении «буквы» begin. Естественнее всего, видимо, понимать конкретную букву как «физический предмет» (состоящий, например, из штрихов, нанесенный краской на бумагу). Некоторые конкретные буквы могут находиться в отношении «одинаковости», тогда они считаются представителями одной и той же абстрактной буквы. Разумеется, отношение «одинаковости» зависит от соглашения, мы вольны считать «а» и «о», «гэ» и «->», «begin» и «начало» представителями одной или разных абстрактных букв соответственно. Подробнее о конкретных и абстрактных буквах, алфавитах и словах см книгу А. А. Маркова «Теория алгорифмов», Jl, 1954, стр. 7—15. — Прим. ред
