Основы ДИСКРЕТНОЙ МАТЕМАТИКИ

ДОНБАССКИЙ ИНСТИТУТ ТЕХНИКИ И МЕНЕДЖМЕНТА

МЕЖДУНАРОДНОГО НАУЧНО-ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

 

 

Основы ДИСКРЕТНОЙ МАТЕМАТИКИ

Конспект лекций

 

 

УТВЕРЖДЕНО

на заседании методичес-

кого совета ДИТМ МНТУ

Протокол N_______

от _____________ 2007г.

 

 

г. Краматорск, 2007

 

 

Конспект лекций по дисциплине «Основы дискретной математики» (для студентов специальностей 06.0804) сост. Воробьёва С.И.. ДИТМ МНТУ

Тема №1. Теория множеств.

План.

1.1.Условные обозначения, принятые в конспекте лекций .

1.2 Множества. Способы задания множеств ...............

1.3 Операции над множествами ..........................

1.4 Действия с цепочками ..............................

1.5 Число элементов множества

 

Условные обозначения, принятые в конспекте лекций

N - множество всех натуральных чисел (N = {1,2,3,...}); Nо - множество всех натуральных чисел и ноль (Nо={0,1,2,3,...}); ї - знак принадлежности (" а ї А " - элемент а принадлежит мно-

Множества. Способы задания множеств

 

Язык множеств - универсальный язык математики. Любое математическое утверждение можно сформулировать как утверждение о некотором соотношении между множествами: о равенстве двух множеств, о непустоте некоторого множества, о непринадлежности элементам множества. Понятие "множество" - одно из базовых понятий в математике и не может быть определено через другие понятия. Интуитивно множество можно определить как совокупность предметов, понятий, явлений, множеств, объединенных одним или несколькими свойствами. В множестве не может быть одинаковых элементов. Порядок следования элементов в множестве не важен. Множества, подмножества будем обозначать большими буквами латинского алфавита (A,B,C,D...), а элементы множеств малыми(a,b,c,d...).Множество B называется подмножеством A, если любой элемент B является элементом A. Этот факт можно записать следующим образом: В с А.

Множества могут быть конечными (состоять из конечного числаэлементов) и бесконечными. Примеры бесконечных множеств - множество натуральных чисел N ( N={1,2,3,4...}), множество натуральных чисел с включением нуля No (No={0,1,2,3...}). Примеры конечных множеств будут приведены ниже.

Число элементов в конечном множестве М называется мощностьюмножества и обозначается ¦ М ¦ или n(M). Множество мощностью 0- 5 -т.е. множество не содержащее элементов называется пустым и обоз-начается так: М = { } или М = 0. Принято считать что пустое множество является подмножеством любого множества, в том числе и пустого.

Множество может быть задано:

1.Списком элементов: A = {a,b,c,d};

S = {Иванов,Петров,Сидоров}.

2.Порождающей процедурой:

M = {(x,y)¦(x)^2+(y)^2 = 1} (задана окружность радиуса R=1);

K = {(a,b)¦, a ї А и b ї B} (задано произведение множеств АхВ);

D = A U B = { x ¦, x ї А или x ї В } (задано объединение двух множеств).

3.Описанием характеристических свойств, которыми должны обладать элементы множества:

Все студенты ДИТМ МНТУ;

Футбольная команда "Шахтер";

Жители города Краматорска.

 

Операции над множествами

 

1.Объединение множеств: A U B = { а ¦ а ї A или а ї B}.

Объединением множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из объединяемых множеств.

D = A U B = { x ¦, x ї А или x ї В }

Операция "объединение" n-арная (т.е. применима к n множествам), коммутативная (при перестановке объединяемых множеств результат не изменяется).

 

Пример: A = {a,ab,ac,c}; B = {ac,ba,b,c}; C = {b,f}

D = A U B U C = C U B U A = {a,ab,ac,c,ba,b,f}.

 

2.Пересечение множеств:

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

A П B = { x ¦ x ї A и x ї B }

Операция "пересечение" n-арная (т.е. применима к n мно-

жествам), коммутативная (при перестановке пересекаемых множеств

результат не изменяется).

 

Пример: A = {a,b,c,f}; B = {b,c,n}; C = {d,f,n};

D = A П B = {b,c}; B П C = { n };

Е = A П B П C = B П C П A = { }.

- 6 -

3.Разность множеств:

Разностью двух множеств называется множество, состоящее из всех элементов, принадлежащих первому множеству и не принадлежащих второму множеству.

A B = { а ¦ а ї A и а не ї В }.

Операция "разность" бинарная (т.е. применима к двум множествам), некоммутативная (при перестановке вычитаемых множеств результат изменяется): A B не равно B A.

 

Пример: A = {a,c,d,e,f}; B = {a,d,m};

D = A B = {c,e,f}; C = B A = { m }.

 

4.Дополнение множества:

Дополнением множества А (до универсального множества W ) называется множество, состоящее из всех элементов множества W, которые не входят в множество А.

_

А = { a ¦ a ї W и не ї A }.

Операция "дополнение" унарная (т.е. применима к одному множеству или части формулы, которую можно трактовать как одно множество). _

Операцию "разность" в формулах можно заменить: A B = A П B.

_

Пример: W = {a,c,d,e,f,k}; B = {a,d,k}; B = {c,e,f}; A = {a,c};

_ _

В U B = W; В П B = { } (пусто);

_

D = A B = A П B = { c }.

 

Используя множества, операции 1-4 и скобки, которые меняют порядок выполнения операций, можно составлять формулы (наибольший приоритет при выполнении имеет операция "дополнение", затем "разность" и затем две операции одного приоритета - "объединение" и"пересечение"; операции одного приоритета выполняются в формуле попорядку слева направо; если в формуле есть скобки, то сначала выполняются операции в скобках в соответствии с их приоритетом; если знак дополнения стоит над частью формулы, то считают, что эта часть взята в скобки (хотя скобки на самом деле отсутствуют))В задачах контрольных работ в формулах используются только три подмножества: А, В, С или P, Q, R универсального множества W).

Очень удобным является наглядное представление таких формул с помощью диаграмм Венна. Диаграмма в общем виде - это прямоугольник, представляющий универсальное множество W с тремя пересекающимися окружностями внутри; область, заключенная в каждой окружности, представляет соответственно множества А, В, С. В результате таких построений площадь прямоугольника разбивается (в самом общем случае) на восемь связных областей, каждая из которых или произвольная их комбинация может быть описана бесконечным множеством формул.

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

 

5.Прямое произведение множеств:

Прямым или декартовым произведением множеств называется множество, элементами которого являются векторы, составленные из элементов перемножаемых множеств: первые компоненты векторов элементы первого множества, вторые - второго и т.д. Для двух множеств процедура имеет вид:A х В = {(а,b)¦a ї A и b ї B}.

Пример: A = {a,b,c,.....,h}; B = {1,2,3,.....,8};

D = A х B = {(a,1); (a,2); (a,3);... (h,8)}.

Допускается запись D = A х B = {a1; a2; a3;... h8}.

Вектор - упорядоченный набор элементов. Элементы образующие вектор называются координатами или компонентами вектора. Число координат называется длиной или размерностью вектора. В отличие от элементов множества координаты вектора могут быть одинаковыми. Пример: B = (0,3,5,3) - вектор размерности 4;

С = (0,3,3,5) - вектор размерности 4.

Векторы В и С различны, т.к. порядок следования координат разный.

Операция 5 также многоместна (перемножить можно несколько множеств). В качестве сомножителей может выступать одно и то же множество, т.е. множество можно возводить в n-ю степень.В качестве примера рассмотрим случай, когда элементами множества являются символы, например V = {a,b,c}. Такое множество будем называть алфавитом. При возведении этого множества в квадрат получим новое множество, состоящее из двухсимвольных цепочек или слов (элементы - векторы записываются без скобок и разделяющих запятых) V^2 = V x V = {aa, ab, ac, ba,..., cc}. При возведении алфавита в куб (последнее множество умножаем на V) получаем трехсимвольные слова-цепочки и т.д. Алфавит в нулевой степени представляет собой множество, состоящее из одного элемента - 8 -пустой цепочки (обозначение @ - эпсилон): V^0 = { @ } Длина цепочки равна количеству элементов, образующих эту цепочку. Пустую цепочку @ - можно вставлять в любое место других цепчек не изменяя этих цепочек.

¦ а ¦ = 1; ¦ aba ¦ = 3; ¦ ab@a ¦ = 3; ¦ @ ¦ = 0.

 

Действия с цепочками

а) конкатенация (сцепление) цепочек: x = aba, y = cab; xy = abacab; б) возведение цепочек в степень:

Число элементов множества

Для любого конечного множества М, число элементов (мощность множества) будем обозначать n(M). Пусть задано несколько множеств (подмножеств универсального множества):… Дано: A, B, n(A), n(B).

План

2.1Отношения .........................................

2.2. Свойства бинарных отношений .......................

2.3. Операции с бинарными отношениями ..................

2.1.Подмножество R c M^n называется n-местным (n-арным) отношением на несущем множестве M. Множество М является несущим для отношений любой арности, которые на нем построены. Говорят, что элементы вектора (a1,a2,a3,...,an) находятся в отношении R , если этот вектор принадлежит множеству R. Для n=1 отношение называют унарным (по сути, такое отношение выделяет из множества М подмножество R по признаку); для n=2 - бинарным (т.е. отношением между двумя элементами множества М) и т.д.

Отношение- то же множество, элементами которого являются векторы размерности n или, при другой записи, цепочки длины n, составленные в алфавите М и отобранные в соответствии с отношением R

 

Пример: Построим бинарное отношение R, которое определим словами как "в латинском алфавите встречается раньше" на несущем множестве M={a,b,c,d}. Примерами элементов отношения R могут быть векторы (a,c), (c,d)... или цепочки ac, cd, bd..., такие, в которых на первом месте стоит буква, встречающаяся в латинском алфавите раньше по сравнению с буквой, стоящей на втором месте.

Отношение R является подмножеством множества M^2:

M^2 = {aa, ab, ac,...,cc}, из которого элементы отбираются в соответствии со следующей процедурой R={xy ¦ x "меньше" y}.

R={ab,ac,ad,bc,bd,cd}

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

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

-- ij¦ a ¦ b ¦ c ¦ d ¦

¦ 1, если ai R aj --+---+---+---+---+

Cij = ¦ a ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦

¦ 0 ,в противном случае --+---+---+---+---+

L- b ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦

--+---+---+---+---+

(строки-i, столбцы - j ) c ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦

--+---+---+---+---+

d ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦

--+---+---+---+----

На рисунке представлена матрица для отношения R из предыдущего примера.

 

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

Для каждого бинарного отношения R можно построить обратное отношение R^(-1) (читается: R в степени минус один), поменяв местами в каждом элементе R проекции векторов.

 

Свойства бинарных отношений

Отношение R называется симметричным, если для любого элемента этого отношения (х,y) в множестве R есть соответствующая пара (y,x). Другими словами,… Таким образом, при установлении этого свойства отношения возможны следующие… Матрица смежности симметричного отношения симметрична относительно главной диагонали. Для симметричного отношения…

Операции с бинарными отношениями

 

Поскольку бинарные отношения - это множества, для них определены рассмотренные выше операции над множествами (объединение, пересечение, разность, дополнение). Необходимо заметить:

а) для бинарного отношения R универсальным множеством W всегда будет квадрат несущего множества М т.е операция "дополнение R" всегда определена;

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

Операция "прямое произведение" при ее формальном применении двум отношениям в результате даст отношение арности 4. Естественно потребовать, чтобы при выполнении этой операции арность результата не изменялась. Это достигается применением свойства транзитивности при выполнении операции перемножения отношений.

Пример: Пусть на несущем множестве M={a,b,c,d} заданы два бинарных отношения: R={ab,ac,ad} и Q={ac,ad,cd}. Произведением этих

отношений будет также бинарное отношение S, элементы которого являются подмножеством элементов, полученных в результате формального перемножения множеств R и Q (из всего множества четырех символьных цепочек необходимо отобрать только те, у которых средние элементы одинаковы (при записи средние элементы опускаются):

S = R x Q = {accd,dccd} = {ad,dd}.

Примечание: Для более эффективного выполнения операции аналитического перемножения отношений нет необходимости перечислять все четырехсимвольные цепочки; нужно выбирать только те комбинации, у которых второй символ элемента первого отношения совпадает с первым символом элемента второго отношения.

Операцию "прямое произведение отношений" для двух отношений можно выполнить графически (на графах перемножаемых отношений) по следующему алгоритму: если на графе первого отношения есть дуга, соединяющая пару вершин (x,y), а на графе второго - дуга, соединяющая вершины (y,z), то на графе результирующего отношения изобразить дугу, соединяющую вершины (x,z); продолжать до исчерпания всех вариантов.

Конечный результат перемножения не зависит от способа выполнения операции (аналитический или графический).

Через прямое произведение отношений можно определить степени одного отношения: Q x Q = Q^2; Q x Q x Q = Q^3 и т.д.

Транзитивным замыканием отношения Q (обозначается Q+) называют объединение всех целых степеней отношения Q. Такое определение транзитивного замыкания отношения не дает эффективного алгоритма его построения для заданного отношения (по определению - это бесконечный процесс).

Аналитически это можно записать как объединение степеней мно-

жества:Q+=Q U Q^2 U Q^3 U Q^4 U ... Q^n... или Q+=U Q^i (i ї N).

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

Транзитивно-рефлексивное замыкание отношения Q (обозначается Q*) - это объединение нулевой степени отношения Q и транзитивного

замыкания отношения Q: Q* = Q^0 U Q+. Нулевая степень любого отношения, построенного на несущем множестве М={a,b,c,d} имеет вид:

{aa, bb, cc, dd}.

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

 

Тема №3. Элементы алгебры логики.

План

 

3.1 Простые высказывания; логические связки ...........

3.2 Составные высказывания; таблицы истинности ........

3.3 Логические законы .................................

3.4 Построение заданных составных высказываний ........

3.5 Отношения между высказываниями ....................

3.6 Аргументы .........................................

 

Простые высказывания; логические связки

Простые высказывания будем обозначать p, q, r, ...Основное свойство простого высказывания: высказывание может быть или ложно(False, 0,… Для построения составных высказываний будем использовать пять логических… 1. Конъюнкция ( логическое " И " ) p / q

Составные высказывания; таблицы истинности

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

Логические законы

Пример 2 Построить таблицу истинности для В = ~(p -> q) / q.   Таблица истинности

Отношения между высказываниями

Как было сказано выше, высказывание (простое или составное) полностью характеризуется таблицей истинности (число строк в этой таблице определяется… Так как в таблицах истинности 0 и 1, то при сравнении двух строк таких таблиц возможны следующие варианты:

Аргументы

Под аргументом будем понимать утверждение того, что некоторое высказывание (заключение) следует из других высказываний (посылок). Одной из задач логики является проверка правильности аргументов. Аргумент называется правильным, если конъюнкция посылок связана с заключением отношением "следует".

Тема №4. Элементы теории графов

План

4.1 Общие понятия и определения .......................

4.2 Способы задания графов ...........................

4.3 Элементы графов ...................................

4.4 Операции с частями графа ..........................

4.5 Диаметр, радиус и центр графа .....................

4.6.Параметры протяженности (диаметр, радиус и центр) графа ............................................

 

Общие понятия и определения

Граф G как математический объект - это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет… G(V,E) = < V; E >, n(V) > 0, E c V x V для неориентированного графа E = E^(-1) (бинарное отношение Е - симметрично).

Способы задания графов

 

Множество вершин и множество рёбер для конечных графов задаются как правило перечислением. Возможно задание графа описанием отношения инцидентности.

 

1.Отношение инцидентности задано матрицей смежности:

- столбцы и строки матрицы - вершины графа;

- для смежных вершин - элемент матрицы - 1, для остальных - 0;

- для неориентированного графа эта матрица всегда симметрична;

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

2.Отношение инцидентности задано матрицей инцидентности:

- столбцы матрицы соответствуют вершинам графа,а строки-рёбрам;

- если ребро e(i) инцидентно вершине v(j),то элемент матрицы E(i,j)=1,в противном случае E(i,j)=0.

Таким образом в каждой строке одна или две единицы, остальные - нули (если петля, то две единицы).

Для ориентированного графа при заполнении матрицы:

E(i,j)=-1,если v(i)-начало ребра.

E(i,j)=1,если v(i)-конец ребра.

E(i,j)=a(где a-любое число, кроме -1,1,0),если ребро-петля в вер-

шине v(i).

В остальных случаях E(i,j)=0.

 

3.Список рёбер.

---------T-----------¬

¦ e(i) ¦ v1,vn ¦ e(i)-ребра

+--------+-----------+ v1,vn-пара вершин, соединяемых ребрами.

¦ 1. ¦ ¦

¦ 2. ¦ ¦

¦ ... ¦ ¦

L--------+------------

 

Элементы графов

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

Операции с частями графа

 

1.Дополнение. _

Если задан граф G и его часть H, то дополнение части H - H со-

держит части ребер графа G, которые не принадлежат H.

2.Объединение.

H1 U H2 = H

V(H1) U V(H2) = V(H), E(H1) U E(H2) = E(H),

- 23 -

где H1, H2 - части графа H;

V(H), V(H1), V(H2) - множества вершин;

E(H), E(H1), E(H2) - множества рёбер.

_

H U H = G (объединение части графа и его дополнения).

 

3.Пересечение.

H1 П H2 = H;

V(H1) П V(H2) = V(H) (если Н1 и Н2 не имеют общих вершин, то эта операция не определена);

E(H1) П E(H2) = E(H).

 

Маршрутом в графе G называется такая конечная последовательность (e1,e2,...,en),что каждые два соседних ребра имеют общую инцидентную вершину.

Вершина Vo, инцидентная ребру e1 и не инцидентная ребру e2, называется началом маршрута в графе G.

Вершина Vn, инцидентная ребру en и не инцидентная ребру e(n-1),называется концом маршрута.

Число ребер маршрута называется его длиной.

Если вершины Vo и Vn совпадают, то маршрут называется циклическим (или просто циклом).

Отрезок конечного или бесконечного маршрута сам является маршрутом.

Маршрут называется цепью, если все ребра различны, и простой цепью, если все вершины (а значит и ребра) различны.

Другими словами, в цепи ребро может встретиться не более одного раза, в простой цепи вершина - не более одного раза.

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

В частном случае расстояние и протяженность между вершинами

могут быть одинаковыми.

 

 

Диаметр, радиус и центр графа

Задан единичный связный неориентированный граф G. Минимальная длина простой цепи с началом V' и концом V" называется… Диаметр графа - максимальное из расстояний между любыми парами вершин:

Параметры протяженности (диаметр, радиус и центр) графа

Задан единичный связный неориентированный граф G. Максимальная длина простой цепи с началом V' и концом V" называется протяженностью между… Диаметр протяженности графа - максимальная из протяженностей между любыми… L(G) = max g(V',V").

План.

5.1 Конечные автоматы - распознаватели ...............

5.2 Эквивалентность состояний КА ......................

5.3 Недостижимые состояния ............................

5.4 Недетерминированный конечный автомат

 

Конечные автоматы - распознаватели

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

Эквивалентность состояний КА

Два состояния конечного автомата эквивалентны тогда и только тогда, когда, начав работу из этих состояний, конечный автомат будет допускать одни и… Эквивалентные состояния, принадлежащие одному КА, не нарушая эквивалентности,… Поиск эквивалентных состояний производится в процессе многократного разбиения множества состояний КА в зависимости от…

Недостижимые состояния

Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов. Такие… Шаг 1: записать одноэлементное множество, в которое входит начальное… Шаг 2: дополнить это множество состояниями, в которые переходит автомат из состояний, уже присутствующих в множестве…

Недетерминированный конечный автомат

Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре входной символ -… В процессе построения такого недетерминированного конечного автомата должны… а) входной алфавит V (конечное множество входных символов и символ "конец цепочки");

Тема № 6 Автоматы с магазинной памятью

План

 

6.1 Автоматы-распознаватели с магазинной памятью

6.2 Автоматы-трансляторы с магазинной памятью

6.3 Задачи на построение МП-распознавателей

6.4 Задачи на построение МП-трансляторов -4

 

Автоматы-распознаватели с магазинной памятью

МП-автомат задается : 1.Конечным множеством входных символов (включая символ конца цепочки… 2.Конечным множеством магазинных символов (включая маркер

Автоматы-трансляторы с магазинной памятью

В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество. Такие действия может выполнять МП-транслятор, на выходе которого будет… МП-транслятор задается :

Задачи на построение МП-распознавателей.

г========T=============================================¬ ¦ N п/п ¦ Построить МП-распознаватель для следующих ¦ ¦ ¦ регулярных множеств ¦

Задачи на построение МП-трансляторов

г=========T=============================================¬ ¦ N п/п ¦ Построить МП-транслятор, который преобразует¦ ¦ ¦ цепочку А в цепочку В. ¦

Тема № 7. Грамматики

План

7.1 Общие сведения

7.2 Классификация грамматик

7.3 Эквивалентные преобразования КС-грамматик

7.3.1 Удаление или добавление бесполезных (непродуктивных

и недостижимых) нетерминалов

7.3.2 Добавление нетерминала

7.3.3 Подстановка правил

7.3.4 Изменение направления рекурсии

 

Общие сведения

В расширенном представлении под языком понимают всякое средство общения, состоящее из:

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

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

-соответствия между последовательностями знаков и смыслами,

делающими осмысленными допустимые последовательности знаков.

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

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

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

Каждое правило из множества P имеет вид x -> y, где x,y -цепочки, состоящие из терминальных и нетерминальных символов. В дальнейшем будем рассматривать грамматики, содержащие только правила, левые части которых состоят из одного нетерминального символа (контекстно-свободные грамматики). При этом должно быть хотя бы одно правило, левая часть которого - начальный символ грамматики.

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

 

Пример: задана грамматика G[Z] VN={Z,A,B}; VT={a,b,c}; Z-начальный символ.

P = { Z -> ABc; (1)

A -> aB; (2)

B -> b }; (3)

 

С помощью грамматики G можно продуцировать (получать) цепочки в алфавите терминалов. Дерево вывода для одной из цепочек

(abbc) имеет вид:

 

 

Z

/ |

/ |

/ |

A B c

/ | |

/ | |

/ | |

a B b

|

|

|

b

Порядок вывода можно записать в следующем виде:

1 2 3 3 (номера примененных правил)

Z -> ABc -> aBBc -> abBc -> abbc

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

Сокращенно вывод можно записать, пропустив промежуточные результаты так Z +-> abbc (цепочка abbc выводима из начального символа Z в заданной грамматике G).

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

-начинать обход с самого левого узла;

-обход надо совершать так, чтобы при переходе к следующему узлу образованное поддерево не включало как элемент предыдущее поддерево.

Фраза часть сентенциальной формы, выводимая из одного нетерминала за несколько шагов. Для простой фразы шаг вывода равен 1.

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

1. Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.

 

2. Каждому дереву соответствует один или более выводов.

3. Каждому дереву соответствует единственный правый и единственный левый выводы.

4. Если каждой цепочке выводимой в данной грамматике соответствует единственное дерево вывода, то такая грамматика называется однозначной ( в правой части каждого правила такой грамматики содержится не более одного нетерминала).

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

В процессе функционирования грамматики возможны два варианта:

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

а) вывод цепочки из начального символа грамматики (построить дерево вывода или вывод начиная с корня) - нисходящий вывод;

б) вывод можно также делать начиная с кроны дерева (готового предложения). Если удается прийти к начальному символу, то предложение принадлежит заданной грамматике - восходящий вывод. В обеих случаях строится дерево вывода.

2. Строить цепочки, которые принадлежат к языку, порождаемому заданной грамматикой.

 

Классификация грамматик

 

Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик:

 

г==========================================================¬

¦ 0-тип - грамматики с фразовой структурой. ¦

¦ x -> y; x и y - любые цепочки терминалов и нетерм. ¦

¦ ---------------------------------------------------------¦

¦ ¦ 1-тип - контекстно-зависимые грамматики ¦

¦ ¦ x -> y; ¦x¦ <=¦y¦ (правая цепочка не короче левой);¦

¦ ¦ -------------------------------------------------------¦

¦ ¦ ¦ 2-тип - контекстно-свободные грамматики ¦

¦ ¦ ¦ A -> y; A - нетерминал, y - любая цепочка; ¦

¦ ¦ ¦ -----------------------------------------------------¦

¦ ¦ ¦ ¦ 3-тип - автоматные грамматики ¦

¦ ¦ ¦ ¦ A -> aB A => b; a,b-терминалы; A,B - нетерминалы ¦

L==========================================================-

Каждый тип грамматик включает грамматики более высоких типов,

как частные случаи.

 

Эквивалентные преобразования КС-грамматик

Для построения распознавателей грамматик, других целей очень часто необходимо преобразовать правила исходной грамматики к соответствующему виду. При… Две грамматики эквивалентны если они порождают один и тот же язык (одни и те… Рассмотрим ряд процедур, которые всегда приводят к эквивалентным преобразованиям.

Удаление или добавление бесполезных (непродуктивных и не-

Достижимых) нетерминалов

В множестве Р правил грамматики G непродуктивным называют нетерминал из которого нельзя получить цепочку терминалов. Для поиска в множестве правил… Свойство А: Если все символы правой части правила продуктивны, то продуктивен…  

Добавление нетерминала

 

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

Пример: Пусть в исходной грамматике G одно из правил имеет вид A -> abВc. Обозначив bB через новый нетерминал N, заменим это правило двумя: A -> aNc; N -> bB.

Процедуру добавления нетерминала к множеству правил можно применять многократно.

 

Подстановка правил

 

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

 

В множество Р можно добавить правило A -> х, если A +-> х. (если цепочка х выводима из А с применением других правил множества Р).

 

Изменение направления рекурсии

Для построения распознавателей в правилах грамматики не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике…   A -> y1¦y2¦....¦ys¦y1B¦y2B¦....¦ysB

Тема № 8 Построение распознавателей для грамматик

План

8.1 Построение КА для распознания автоматных грамматик .

8.2 Построение КА-распознавателей для праволинейных грамматик

8.3 Построение МП-распознавателей для S-грамматик

8.4 Построение МП-распознавателей для q-грамматик .

8.5 Задачи преобразование грамматик и построение МП-распознавателей ................................

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

 

Построение КА для распознания автоматных грамматик

Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий: 1.Начальный символ грамматики - начальное состояние КА. 2.Терминальные символи грамматики - алфавит КА (без символа

Построение КА-распознавателей для праволинейных грамматик

Праволинейную грамматику всегда можно преобразовать в автоматную, для которой построение КА-распознавателя рассмотрено в предыдущем разделе.… A -> x<yzB>; <yzB> -> y<zB>; <zB> -> zB (в… Таким образом происходит замена исходного правила несколькими, которые сответствуют правилам автоматной грамматики. В…

Построение МП-распознавателей для q-грамматик

КС-грамматика (грамматика второго типа) называется q-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и… Правила имеют вид Х -> y&, где y - терминал; & - любая це-почка… Замечание: q-грамматика отличается от S-грамматики только наличием в множестве Р эпсилон-правил; этот факт существенно…