XVYggbpFw2

УДК 004.4:519.713(075.8)

ББК 32.973я73 Б44

Печатается по решению Совета по научно-исследовательской работе и редакци- онно-издательской деятельности Мурманского арктического государственного университета

Рекомендовано учебно-методическим советом МАГУ к использованию в учебном процессе (протокол № 3 от 24.04.2019 г.)

Рецензенты: Ю.В. Романовская, кандидат физико-математических наук, заведующий кафедрой математики, информационных систем и программного обеспечения Мурманского государственного технического университета (протокол № 1 от 11.09.2019 г.);

И.М. Лазарева, кандидат физико-математических наук, доцент, заведующий кафедрой математики, физики и информационных технологий Мурманского арктического государственного университета

Беляев В.Я.

Дискретная математика. Грамматики и автоматы: учебное пособие / В. Я. Беляев. – Мурманск: МАГУ, 2019. – 104 с.

Учебное пособие является введением в раздел дискретной математики, посвященный способам определения формальных языков. Рассматриваются такие инструменты, как контекстно-свободные грамматики, регулярные выражения и конечные автоматы. Особый упор делается на применение этих понятий в программировании, что позволяет считать заключительные параграфы пособия введением в так называемое ав- томатно-ориентированное программирование.

Отпечатано с готового оригинал-макета.

СОДЕРЖАНИЕ

Литература…………………………………………………………………………………………………..104

ВВЕДЕНИЕ

Вназвании пособия “Грамматики и автоматы” перечислены два способа определения языков. Понятие языка в дискретной математике звучит очень просто. Язык – это произвольное множество слов. Вообще – любое. При всем том, что слово – любая последовательность символов. Такое представление о языке используется в математической логике с 19 века, пронизывая почти все конструкции дискретной математики. Но особенно его значение возросло в наше время – в век компьютеров.

Разного рода языки являются по существу основой любой системы искусственного интеллекта. То, что (не стараясь быть слишком точным) называют дискретной математикой, является необходимым звеном, связывающим человека и какое-либо автоматическое устройство. Например, люди любят решать свои житейские проблемы, прибегая к числам. А что такое, натуральные числа: ноль, один, два и т.д.? Это абстракции, суть которых понимает только человек. К примеру, число два – это единственный общий признак, присущий всем парам предметов.

Для компьютера же числа - это слова 0, 1, 2, …, 10,11,12, … . Он их чудесным образом и с непостижимой скоростью складывает, множит, делит, совершенно не понимая, что это значит. Компьютер работает с множеством слов. И хотим мы этого или нет, но эти слова (т.е. записи чисел в десятичной системе счисления) образуют некий самостоятельный мир. Он живет по своим законам. Он вполне логически самодостаточен. Ему не надо никакой философии. Он объект чистой математики. И благодаря этому

сним могут работать вычислительные системы, абсолютно лишенные абстрактного мышления.

Кто-то скажет: “Слова вроде 10, 12, 99 и есть числа”. С этим трудно согласиться. Это только наша привычка – не отличать запись чисел от самих чисел. Например, в двоичной системе счисления эти же числа записываются другими словами: 1010, 1100, 1100011. Записи одних и тех же чисел в десятичной системе счисления и в двоичной системе счисления – это совершенно разные языки.

Всвязи с понятием языка существуют два понятия: синтаксис языка и семантика языка. Семантика – это интерпретация, смысл слов. Синтаксис

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

Например, язык логики предикатов наилучшим образом раскрывает суть логического мышления. Благодаря открытию этого языка основания

математики получили достаточно прочный фундамент. А поразительные теоремы Геделя о неполноте еще долго будут предметом обсуждения философов.

Чисто синтаксические конструкции, подобные машинам Тьюринга, наилучшим образом отражают понятие алгоритма. Машина Тьюринга – теоретический образ любого компьютера. А глядя на чудеса современных компьютеров, большинство людей склонно наделять их какими-то сверхъестественными способностями, не подозревая, что способности этой железки не идут дальше умения тасовать определенные слова по предписанным человеком правилам. Невольно закладывается подозрение, что синтаксис и есть главная суть понятия алгоритма.

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

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

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

1. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ

Понятие формальной грамматики возникло в работах американского лингвиста Ноама Хомского в конце 50-тых годов 20-го века. Широкую же известность они получили после того, как Джон Бэкус - “отец” языка Фортран - на их основе предложил формальный способ описания языков программирования. Нотацию Бэкуса для описания языка Алгол стали обозначать аббревиатурой БНФ (Бэкуса нормальная форма). В 1960 г. датский астроном Петер Наур в этой нотации описал новый вариант Алгола. После этого сокращение БНФ стали расшифровывать как Бэкуса-Наура форма.

С тех пор язык Бэкуса-Наура стал очень популярен среди программистов и грамотных пользователей компьютерной техники. На элементы этого языка можно наткнуться в самых неожиданных местах. Вместе с ним в дискретной математике важное место заняла математическая модель этого языка – теория формальных грамматик. Начнем со строгих математических определений.

Алфавит – это множество, элементы которого мыслятся как символы. Слово или цепочка в алфавите – это конечная последовательность его символов. Допускаются пустые слова – цепочки, не содержащие ни одного символа. Слова записываются привычным образом – просто перечисляются символы слова. Например,

aabc , abac , aa , a , bb , bbb

шесть различных слов алфавита {a, b, c}. Пустое слово будем обозначать символом .

Количество букв в слове w называется его длиной и обозначается |w|. Например,

|aabc| = 4 , |abac| = 4 , |aa| = 2 , |a| = 1 , |bb| = 2 , |bbb| = 3, | | = 0.

Множество всех слов алфавита обозначается *. Множество не-

+.

Язык в алфавите - это произвольное подмножество множества всех слов *.

Пример 1.1. = { a, b, c, +,- , *, / , (, ) }. L - множество всех правильных арифметических выражений языка Паскаль, составленных из этих символов. Теперь a*(b+c) L, а a*(b+) L.

Определение 1.1. Формальной грамматикой G называется чет-

вёрка

<T, N, P, S >

где T и N — конечные алфавиты, причем T ∩N = , S N, P – конечное множество пар вида

пустая.

Задача конкретной формальной грамматики – описать какое-то множество слов алфавита T, т.е. язык. В практических задачах слова этого алфавита играют роль каких-то важных объектов. Например, слово - это синтаксически правильная программа языка Паскаль. Определяемое множество слов – это множество всех программ на Паскале.

Буквы из T называются терминалами (терминальными, конечными). При абстрактном рассмотрении какой-то грамматики, терминальные символы будем обозначать маленькими латинскими буквами (a, b, c, …).

вода (числом шагов). Считаем, что каждое слово выводится само из себя за 0 шагов.

Определение 1.2. Язык, порожденный грамматикой G, - это множество всех слов алфавита Т (терминалов), выводимых из начального нетерминала S.

Таким образом, если мы, стартуя с символа S, последовательно по правилам грамматики будем получать ряд слов и остановимся, когда получится цепочка без нетерминалов, то эта последняя цепочка принадлежит языку, порожденному грамматикой.

Пример. Пусть G = <{S, A}, {a, b}, P, S >, причем P состоит из пра-

вил:

Эти выводы показывают, что в языке, порожденном грамматикой G, лежат слова aabbcc и aaabbbccc. А вообще язык этой грамматики, как не-

трудно доказать, – это множество всех слов вида anbncn, включая пустое слово (при n = 0).

Определение 1.3. Грамматики G1 и G2 , имеющие один и тот же

алфавит T терминалов, называются эквивалентными, если они порождают один и тот же язык.

2. КЛАССИФИКАЦИЯ ПО ХОМСКОМУ

Формальные грамматики по ограничениям, накладываемым на правила, образуют несколько классов (иерархия Хомского):

Класс 0 – грамматики общего вида. Никаких ограничений не накладывается. Это класс всех формальных грамматик.

Класс 1 – контекстно-зависимые грамматики. Все правила в такой грамматике должны иметь вид

A

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

Класс 2 – контекстно-свободные грамматики (КС-грамматики, контекстно-независимые, бесконтекстные), имеющие в левой части любого правила слово из единственной буквы - нетерминала. Другими словами, контекстно-свободная грамматика – это множество правил вида

A

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

Класс 3 – регулярные грамматики, Любое правило которых имеет один из видов:

Правила вида A , называются –правилами. Это замена нетерминала пустым словом. Иначе, применение –правила – это просто вычеркивание соответствующего нетерминального символа.

Из определений иерархии Хомского очевидно, что:

o любая грамматика класса 3 является грамматикой класса 2;

o любая грамматика класса 2 без –правил является грамматикой класса 1;

o любая грамматика класса 1 является грамматикой класса 0. Далее мы увидим, что наличие –правил в контекстно-свободной

грамматике не слишком сильно влияет на множество выводимых слов. Точнее, если пустая цепочка не выводима из начального нетерминала, то

грамматику легко переделать в эквивалентную без –правил. Если пустая цепочка все же выводится, то ее можно переделать в эквивалентную с одним единственным –правилом S .

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

щуюся иерархию.

Принято классом грамматики считать минимальный класс, в который она попадает. Например, грамматика G считается контекстносвободной, если она является грамматикой класса 2, но не является грамматикой класса 3. Это не препятствует тому, что G может быть эквивалентной некоторой регулярной грамматике.

Замечание 2.1. Определение контекстно-зависимой грамматики дают так: это грамматики, все правила которых имеют вид

где , - любые слова из терминалов и нетерминалов, но в обязательно есть нетерминалы, и длина не меньше, чем длина . Более точно, такие грамматики называют несокращающими. Можно доказать, что все несокращающие грамматики эквивалентны грамматикам класса 1 и наоборот.

Замечание 2.2. Грамматики класса 3 называют право-регулярными. Вместе с ними определяют аналогичное понятие лево-регулярной грамматики – когда все правила имеют вид

A

В конце пособия будет доказано, что любая право-регулярная грамматика эквивалентна лево-регулярной и наоборот. Поэтому эти грамматики и называют просто регулярными.

Замечание 2.3. Часто используется понятие так называемой линейной грамматики. Это грамматика, в которой все правила вывода имеют один из видов

Существуют линейные грамматики, не эквивалентные никакой регулярной. Такой, например, является грамматика G