авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 |

«УДК 002; 004.3(075.8) МИНОБРНАУКИ РОССИИ ББК 32.81; 32.97я73 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ ...»

-- [ Страница 4 ] --

2.1.6.2. Множество натуральных чисел Определение натурального множества. Всякое множество, удовлетворяющее свойст вам 1. 1 N 2. n, n N n + 1 N 3. n, n N, n 1 y N, n = y + называется множеством натуральных чисел.

Множество N удовлетворяет аксиомам Пеано:

1. 1 N.

2. n, n N n’ N.

3. n N n’ 1.

4. n N, m N, n’ = m’ n = m.

1 A A= N.

5.

n A n ' A где n’ = n + 1.

Данное множество – множество натуральных чисел N = {1, 2, 3, …}.

Замечание. Множество N ={0, 1, 2, 3…} называют расширением натурального множе ства.

Стандартные обозначения некоторых множеств.

N – множество всех натуральных чисел.

Z – множество всех целых чисел.

Z+ – множество целых неотрицательных чисел.

Z– – множество целых неположительных чисел.

Q – множество всех рациональных чисел.

R – множество всех действительных чисел.

R+ – множество неотрицательных действительных чисел.

R– – множество неположительных действительных чисел.

2.1.6.3. Конечные и бесконечные множества Конечное множество – множество, состоящее из конечного числа элементов.

Пример. A = {1, 2, 3, 4, 5}.

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

Бесконечное множество – непустое множество, не являющееся конечным.

Пример. Множество натуральных чисел является бесконечным.

Множество состоит из элементов. Принадлежность элемента а множеству М Обозначается аМ.

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

Если А В и А В, то А называют строгим или истинным подмножеством В и обо значают А В.

Множество, состоящее из конечного числа элементов, называют конечным. Если чис ло элементов множества бесконечно, то его называют бесконечным. Число элементов в ко нечном множестве М, называют мощностью М и обозначают | M |.

Множество мощности 0, то есть не содержащее элементов, называют пустым и обо значают.

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

2.1.6.4. Включение и равенство множеств Пусть Х и У – два множества. Если каждый элемент х множества Х является элементом множества У, то говорят, что множество Х содержится во множестве У и пишут: Х У или У Х. Говорят также, что Х включено в У или У включает Х, или что Х является подмноже ством множества У. Знаки включения или относятся только ко множествам и их не следует смешивать со знаками принадлежности и. Если, например, А – множество всех студентов вуза, а В – множество студентов-первокурсников этого вуза, то В есть подмноже ство А, т.е. В А. Пустое множество считают подмножеством любого множества Х, т.е. Ш Х, каким бы ни было множество Х. Ясно также, что каждое множество является подмно жеством самого себя: Х Х.

Если для двух множеств Х и У одновременно имеют место два включения Х У и У Х, т.е. Х есть подмножество множества У и У есть подмножество множества Х, то множества Х и У состоят из одних и тех же элементов. Такие множества Х и У называют равными и пи шут: Х = У. Например, если А = {2;

3}, а В = {х | хІ –5х + 6 = 0}, то А = В.

Если Х У, но Х У, т.е. существует хотя бы один элемент множества У, не принад лежащий Х, то говорят, что Х есть собственное подмножество множества У, и пишут: Х У.

Например: N Z, Z Q, Q R. Далее нам потребуется множество, которое содержит в ка честве своего подмножества любое другое множество. Такое «всеобъемлющее» множество будем называть универсальным и обозначать буквой U.

Диаграммы Эйлера-Венна Для наглядного представления множеств используют диаграммы Эйлера-Венна. В этом случае множества обозначают областями на плоскости и внутри этих областей условно рас полагают элементы множества. Часто все множества на диаграмме размещают внутри пря моугольника, который представляет собой универсальное множество U. Если элемент при надлежит более чем одному множеству, то области, отвечающие таким множествам, должны перекрываться, чтобы общий элемент мог одновременно находиться в соответствующих об ластях. Выбор формы областей, изображающих множества на диаграммах, может быть про извольным (круги, внутренности эллипсов, многоугольники и т.п.). Покажем, например, с помощью диаграммы Эйлера-Венна, что множество А является подмножеством множества В:

С помощью такой диаграммы становиться наглядным, например, такое утверждение:

если А В, а В С, то А С.

Строгое доказательство этого утверждения, не опирающееся на диаграмму, можно про вести так: пусть х А;

так как А В, то х В, а так как В С, то из х В следует, что х С;

значит, из того, что х А, следует х С, а поэтому А С.

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

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

Символическая запись этого определения: А В = {х | хА или х В}.

Здесь союз «или» понимается в смысле «неразделительного или», т.е. не исключается, что х может принадлежать и А и В. Отметим, что в таком случае элемент х, входящий в оба множества А и В, входит в их объединение только один раз (поскольку для множества не имеет смысла говорить о том, что элемент входит в него несколько раз).

Поясним определение объединения множеств с помощью диаграммы Эйлера-Венна:

На диаграмме объединение множеств А и В выделено штриховкой.

Если множество А определяется характеристическим свойством Р(х), а множество В – характеристическим свойством Q(х), то А В состоит из всех элементов, обладающих, по крайней мере, одним из этих свойств.

Примеры объединений двух множеств:

1) Пусть А = {2;

5;

7}, В = {3;

5;

6}. Тогда А В = {2;

3;

5;

6;

7}.

2) Пусть А = [–1/4;

2], В = [–2/3;

7/4]. Тогда А В = [–2/3;

2].

3) Пусть А = {х | х = 8k, k Z}, B = {x | x = 8n–4, n Z}. Тогда A B = {x | 4m, m Z}.

Операция объединения множеств может проводиться не только над двумя множествами. Определение объединения множеств можно распространить на случай любого количества множеств и даже – на систему множеств. Система множеств определяется так:

если каждому элементу множества М отвечает множество А, то совокупность всех таких множеств мы будем называть системой множеств.

Объединением системы множеств {А} называется множество A, состоящее из всех U M элементов, принадлежащих хотя бы одному из множеств А. При этом общие элементы не скольких множеств не различаются.

Таким образом, элемент х M A тогда и только тогда, когда найдется такой индекс U М, что х A0.

n В случае, когда М конечно и состоит из чисел 1, 2, …, n, применяется запись U Ai Если i = UA.

M = N, то имеем объединение последовательности множеств i i = Рассмотрим ещё один пример: пусть М = (1;

2) и для каждого є М определим множе ство А = [0;

];

тогда A = [0;

2).

UM Из определения операции объединения непосредственно следует, что она коммутативна, т.е. А1 I A2 = A2 I А1, и ассоциативна, т.е. (А1 U A2) U А3 = А1 U (A2 U А3).

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

Символическая запись этого определения: А I В = {х | х А и х В}.

Поясним определение пересечения множеств с помощью диаграммы Эйлера-Венна:

АВ На диаграмме пересечение множеств А и В выделено штриховкой.

Если множество А задается характеристическим свойством Р(х), a множество В – свой ством Q(х), то в А В входят элементы, одновременно обладающие и свойством Р(х), и свойством Q(х).

Примеры пересечений двух множеств:

1) Пусть А = {2;

5;

7;

8}, В = {3;

5;

6;

7}.Тогда А В = {5;

7}.

2) Пусть А = [–1/4;

7/4], В = [–2/3;

3/2]. Тогда А В = [–1/4;

3/2].

3) Пусть А = {х | х = 2k, k є Z}, B = {x | x = 3n, n є Z}. Тогда А В ={x | x = 6m, m Z}.

4) Пусть А – множество всех прямоугольников, В – множество всех ромбов. Тогда А В – множество фигур, одновременно являющихся и прямоугольниками, и ромбами, т.е. мно жество всех квадратов.

Операцию пересечения можно определить и для произвольной системы множеств {А}, где М. Пересечением системы множеств {А}, называется множество M A, I состоящее из всех элементов, принадлежащих одновременно каждому из множеств А, I A = {x | x А для каждого М}.

М, т.е.

M n IA.

В случае, когда М конечно и состоит из чисел 1, 2, …, n, применяется запись i i = Если M = N, то имеем пересечение последовательности множеств I A. i i = В рассмотренном выше примере системы множеств А = [0;

], М = (1;

2) I получим: M A = [0;

1].

Операция пересечения множеств, как и операция объединения, очевидно, коммутативна и ассоциативна, т. е. А1 I A2 = A2 I А1 и (А1 I A2) А3 = А1 I (A2 I А3).

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

А\В = {х | х А и х В}, что можно пояснить на диаграмме Эйлера-Венна следующим образом:

На диаграмме разность А\В выделена штриховкой.

Примеры разностей множеств:

1. Пусть А = {1;

2;

5;

7}, В = {1;

3;

5;

6}. Тогда А\В = {2;

7}, а В\А = {3;

6}.

2. Пусть А = [–1/4;

2], В = [–2/3;

7/4]. Тогда А\В = (7/4;

2], а В\А = [–2/3;

–1/4).

3. Пусть А – множество всех четных целых чисел, В – множество всех целых чисел, делящихся на 3. тогда А\В – множество всех четных целых чисел, которые не делятся на 3, а В\А – множество всех нечетных целых чисел, кратных трем.

Дополнение множества Пусть множество А и В таковы, что А В. Тогда дополнением множества А до множества В называется разность В\А. В этом случае применяется обозначение СBА = В\А.

Если в качестве множества В берётся универсальное множество U, то применяется обозначение СА = СUА = U\А и такое множество просто называют дополнением множества А. Таким образом, символическая запись определения дополнения множества будет следующей: СА = {x | x A}.

На диаграммах Эйлера-Венна можно так пояснить определения СВА и СА:

2.1.6.6. Законы де Моргана Законы де Моргана (правила де Моргана) – логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания.

Определение 6.1.

Огастес де Морган первоначально заметил, что в классической пропозициональной ло гике справедливы следующие соотношения:

not (P and Q) = (not P) or (not Q) not (P or Q) = (not P) and (not Q) Обычная запись этих законов в формальной логике:

¬( P Q) = (¬P) (¬Q), ¬( P Q) = (¬P) (¬Q), или x y = x y x y = x y в теории множеств:

( A B )C = AC B C, ( A B )C = AC B C.

x1 x 2... x n = x1 & x 2 &... & x n Правило де Моргана x1 x 2... x n = x1 & x 2 &... & x n Если существует операция логического умножения двух и более элементов, операция «и» – (A&B), то для того что бы найти обратное от всего суждения ~(A&B), необходимо най ти обратное от каждого элемента и объединить их операцией логического сложения, опера цией «или» – (~A + ~B). Закон работает аналогично в обратном направлении: ~(A+B) = (~A&~B)) Определение подмножества. Множество А является подмножеством множества В, ес ли любой элемент, принадлежащий множеству А, принадлежит множеству В.

Формальная запись: A B x | xA xB.

Если A является подмножеством B, то B называется надмножеством A.

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

Отношение нестрогого включения обозначается “”.

Отношение строгого включения обозначается “”.

A B обозначает, что множество A содержится в B, при чем А может быть равным множеству B. Строгое включение исключает такое равенство.

Если A B, A, то A – собственное подмножество множества В.

Свойства отношения включения.

1. A выполняется A A (рефлексивность).

2. A, B выполняется A B B A A = B (антисимметричность).

3. A, B, C выполняется A B B C A C (транзитивность).

Пример. Пустое множество является подмножеством любого множества. Множество {2, 4, 6,..., 2n,...} является собственным подмножеством множества натуральных чисел {1, 2, 3, 4…}.

Бинарным отношением в множестве E называется всякое подмножество B из произ ведения.E x E Бинарное отношение R называется отношением эквивалентности в множестве E, если подмножество R :

a) рефлексивно: (a, a) Ra R ;

б) симметрично: ((a, b) R) ((b, a) R) ;

в) транзитивно: ((a, b) R (b, c) R) ((a, c) R).

Вместо (a, b) R часто пишут a ~ b или a = b.

Бинарное отношение называется отношением порядка в множестве E, если оно:

a) рефлексивно: (a, a) a E ;

б) транзитивно: ((a, b) (b, c) ) ((a, c) ) ;

в) антисимметрично: ((a, b) (b, a) ) (a = b).

При этом говорят, что отношение упорядочивает E. Вместо (a, b) часто пишут a b или a b.

Если a, b E всегда (a, b) или (b, a), то говорят, что множество E вполне упорядочено.

2.1.6.7. Отношение порядка Отношение P A2 называется отношением порядка на множестве А, если выполнены следующие условия:

а) для любого x A P( x, x) = 1 (рефлексивность);

б) для любых x, y, z A, если P( x, y ) = 1 и P( y, z ) = 1, то P( x, z ) = 1 (транзитивность);

в) для любых x, y A, если P( x, y ) = 1 и P( y, x) = 1, то x = y (антисимметричность).

Бинарное отношение a на множестве X называется отношением порядка, если оно транзитивно:

(a, b, c X )(ab & bc ac) и антисимметрично:

(a, b X )(ab & ba a = b).

Если P – отношение частичного порядка, то вместо P ( x, y ) = 1 принято писать x y.

Тогда условия а), б), в) примут вид:

а) x x ;

б) x y и y z влечет x z ;

в) x y и y x влечет x = y.

Если на множестве A задано отношение частичного порядка, то оно называется час тично упорядоченным множеством и обозначается ( A;

).

Примеры.

1. На множестве N, Z, Q, R задан естественный порядок, который вы изучали еще в школе. Мы его так и будем называть – естественный порядок – и обозначать, как обычно,.

2. Пусть A – произвольное множество и P ( A) = {x | x A} – множество всех подмно жеств множества A. На P( A) определено отношение порядка следующим условием: X Y тогда и только тогда, когда X Y. Очевидным образом выполняются следующие условия:

а) X X ;

б) X Y Y Z X Z ;

в) X Y Y X X = Y.

То есть отношение включения подмножеств есть отношение частичного порядка. Этот пример имеет принципиальное отличие от естественных порядков, рассмотренных в первом примере. В первом примере любые два числа сравнимы по величине, то есть имеет место:

для любых x, y, x y y x.

В примере 2 ситуация иная. Пусть A = {a, b, c}, X = {a, b} A, Y = {b, c} A. Мы не можем утверждать, что X Y, но не можем также утверждать, что Y X, то есть X и Y яв ляются несравнимыми. Наличие в некоторых упорядоченных множествах несравнимых эле ментов и дало основание внести термин частично упорядоченного множества.

A = {0, 1}n = {(1, 2,..., n ) | i = 0 i = 1}.

3. Пусть Определим:

(1, 2,..., n ) ( 1, 2,..., n ) тогда и только тогда, когда i i i = 1, 2,..., n.

4. На одном и том же множестве можно задать разные отношения порядка. Например, на множестве N кроме естественного порядка можно задать следующее отношение: m n в том и только в том случае, когда n делится на m, то есть существует x N, такое, что n = m x. Докажем, что введенное отношение на N есть отношение частичного порядка.

а) m m, так как т делится на m(m = m 1) ;

б) Пусть m l и l n, тогда l = m x и n = l y, где x, y N, следовательно, n = m( x, y ), то есть п делится на т и m n ;

в) Пусть m n и n m, тогда n = m x и m = n y. Отсюда следует, что n = n( x y ), по этому x y = 1, а произведение двух натуральных чисел равно 1 только в том случае, когда x = y = 1, отсюда n = m 1, то есть n = m. Итак все три свойства – рефлексивность, транзи тивность, антисимметричность – частичного порядка выполняются. Значит, отношение де лимости на N является отношением частичного порядка. Это отношение отличается от есте ственного порядка. Например, 3 5, но неверно, что 3 p 5, так как 5 не делится на 3.

5. Конечные упорядоченные множества удобно изображать с помощью схем. Проил люстрируем это двумя примерами.

Пусть A = {2, 3, 4, 6, 8, 9, 10}. Если на А рассмотреть естественный порядок, то полу чим схему:

2 3 4 6 8 9 10.

Мы проводим стрелку от a к b, если a b. Стрелку же от 2 к 4 мы не проводим потому, что существование ее гарантируется стрелками от 2 к 3, от 3 к 4 и транзитивностью.

Теперь на том же множестве А рассмотрим отношение делимости, тогда получим схе му:

Получим совершенно различные схемы на одном и том же множестве А.

Наряду с обычным частичным порядком изучаются строгие частично упорядоченные множества.

Определение 6.2.

Множество ( A;

) называется строго частично упорядоченным, если выполняются ус ловия:

а) для любого x A неверно, что x x (антирефлексивность);

б) для любых x, y, z A влечет x y и y z влечет x z (транзитивность);

в) для любых x, y A не могут одновременно выполняться соотношения x y и y x.

Всякое отношение частичного порядка естественным образом порождает отношение строгого порядка.

Теорема 6.1.

Если x y есть отношение частичного порядка, то отношение x y ( x y x y ) является отношением строгого порядка на А.

Доказательство:

а) Высказывание ( x x x x) ложно, так как ложно второе утверждение конъюнкции x x, значит, ложно x x.

б) Пусть x y и y z, это значит, истинно высказывание x y x y y z y z.

Из первого и третьего членов этой коньюнкции следует x z. Осталось доказать, что x z. Допустим, x = z, тогда получаем x y y x, то есть x = y, но по условию x y. Это противоречие и доказывает, что x z.

( x y y x), в) Допустим, что выполняется конъюнкция то есть ( x y x y y x y x), но первый и третий член коньюнкции влекут x = y. Противоре чие. Значит соотношения x y и y x не могут выполняться одновременно.

Теорема доказана.

Верно и обратное утверждение.

Любой строгий частичный порядок порождает естественным образом просто частич ный порядок.

Теорема 6.2.

Пусть на множестве А задано отношение строго частичного порядка, тогда отноше ние x y ( x y x = y ) является отношением частичного порядка.

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

а) ( x y x = x) – эта дизъюнкция истинна, так как истинен ее второй член х = х, по этому x x.

б) Пусть x y y z, это значит, ( x y x = y )( y z y = z ), что равносильно ( x y y z) ( x y y = z) ( x = y y z) ( x = y y = z).

Отсюда следует: ( x z ) ( x z ) ( x z ) ( x = z ), то есть x z x = z, что и означает xz.

в) Пусть ( x y y x), тогда ( x y x = y ) ( y x y = x).

Это равносильно ( x y y x) ( x = y y x) ( x y y = x) ( x = y y = x).

Первый, второй и третий члены этой дизъюнкции ложны. Первый по свойству в) опре деления строгого порядка, второй и третий по свойству а). Остается равенство х = у.

Теорема доказана.

2.1.6.8. Отношение эквивалентности Отношение P A A называется отношением эквивалентности, если выполняются три аксиомы:

а) для любого x AP( x, x) = 1 – рефлексивность;

б) для любых x, y AP( x, x) = 1 P( y, x) = 1 – симметричность;

в) для любых x, y, z AP( x, y ) = 1 P( y, z ) = 1 p( x, z ) = 1 – транзитивность.

Пример 6.1.

A = Z, P Z Z определяется условием: P ( x, y ) = 1 x y делится на 3. Проверка выполняется для всех трех аксиом.

а) x x = 0 делится на 3, следовательно, P( x, x) = 1.

б) Пусть P( x, y ) = 1, то есть x y делится на 3, значит, и y x = ( x y ) также делится на 3, значит, P( x, y ) = 1 P( y, x) = 1.

в) Пусть P( x, y ) = 1, P( y, z ) = 1, следовательно, x y делится на 3 и y z делится на 3, тогда ( x y ) + ( y z ) = x z тоже делится на 3, то есть P( x, z ) = 1.

Пример 6.2.

Пусть Q Z Z определяется следующим условием: Q( x, y ) = 1 x + y делится на 3.

Данное отношение не является отношением эквивалентности, так как нарушается уже первая аксиома – рефлексивность, так как не для любого x Z x + x делится на 3. Достаточно взять x = 2. Проверьте самостоятельно, выполняются ли остальные две аксиомы.

Пример 6.3.

P R R определяется условием P ( x, y ) = 1 x y Q.

1 x x = 0 Q, значит, P ( x, x) = 1.

а) Так как для любого x R б) Пусть P ( x, x) = 1, то есть x y Q, значит, y x Q, то есть P ( y, x) = 1. Симмет 1 ричность выполняется.

в) Пусть P ( y, x) = 1 и P( y, z ) = 1, значит, x y Q и y z Q, следовательно, ( x y ) + ( y z ) = x z Q, поэтому P ( x, z ) = 1. Транзитивность выполняется.

Пример 6.4.

Пусть A – множество мужчин, P A A определяется условием P ( x, y ) = 1 x – брат y. Если договориться, что мужчина сам себе является братом, то P является отношением эк вивалентности, так как симметричность и транзитивность выполняется очевидным образом.

Если договорится для отношения эквивалентности P вместо P ( x, y ) = 1 писать x ~ y, то аксиомы этого отношения перепишутся более простым и обычным образом:

а) для любого x A x ~ x ;

б) для любых x, y A x ~ y y ~ x ;

в) для любых x, y, z A x ~ y y ~ z x ~ z.

Определение 6.3.

Пусть задана система множеств Ai (i I ), тогда:

а) U Ai (i I ) = {x / i I : x Ai } ;

б) I Ai (i I ) = {x / i I : x Ai }.

Очевидно, что объединение и пересечение конечного числа множеств, например, n, яв ляется частным случаем этих определений, когда индексное множество I = {1, 2,..., n}.

Определение 6.4.

Система множеств Ai, (i I ) называется разбиением множества A, если а) U Ai (i I ) = A ;

б) для любых i, j I ( Ai I A j Ai = Aj ).

Другими словами, различные множества из системы Ai не пересекаются.

Определение 6.5.

Пусть P A2 – отношение эквивалентности на A. Классом эквивалентности, порож денным элементом a A, называется множество [a ] = {x A / x ~ a}.

Теорема 6.3.

Если P – отношение эквивалентности на A, то множество классов эквивалентности об разуют разбиение A.

Доказательство. Докажем вначале U [a ](a A) = A. Так как [a ] A для любого a A, то включение U [a](a A) A очевидно. Возьмем b A. Так как b ~ b, то b [b], значит b U[a](a A), то есть A U[a ](a A), значит и A = U[a](a A) =. Пусть [a] I [b], зна чит существует x [a] I [b], то есть x ~ a и x ~ b. По транзитивности a ~ b. Теперь дока [a] = [b]. x [a ] x ~ a x ~ b x [b].

жем, что Возьмем Если же x [b] x ~ b x ~ a x [a ]. Таким образом, [a] = [b].

Итак, мы доказали, что любое отношение эквивалентности на множестве A порождает естественным образом разбиение A на классы эквивалентности. Оказывается, имеет место и обратное утверждение.

Теорема 6.4.

Пусть система множеств Ai, (i I ) образует разбиение множества A. Отношение P ( x, y ) = 1 существует такое i, что x, y Ai является отношением эквивалентности на A.

Причем элементы разбиения являются классом эквивалентности.

Доказательство. Проверим выполнение всех трех аксиом – рефлексивности, симмет ричности, транзитивности.

Рефлексивность. Пусть a A, тогда a Ai для некоторого i I. Тогда можно запи сать: a, a Ai, то есть P (a, a ) = 1.

Симметричность. Пусть P(a, b) = 1, то есть существует i I, такой, что a, b Ai, тогда и b, a Ai, значит, P(b, a) = 1.

Транзитивность. Пусть P(a, b) = 1 и P(b, c) = 1, значит, существуют такие i и j, что a, b Ai и b, с A j, но тогда b Ai I A j, то есть Ai I A j. По определению разбиения Ai = Aj =, значит, a, b, c Ai, то есть P(a, c) = 1.

Теорема доказана.

2.2. Руководство по практическим занятиям В учебно-методическое пособие по практическим занятиям УМКД включены основные теоретические сведения по темам практических занятий;

задачи для самостоятельного реше ния, заданные по-вариантно;

примеры решения некоторых типовых задач.

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

Теория формальных языков, грамматик и автоматов составляет фундамент синтаксиче ских методов. Основы этой теории были заложены Н. Хомским в 40–50-е годы XX столетия в связи с его лингвистическими работами, посвященными изучению естественных языков.

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

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

Распределение тем практических занятий по времени № Наименование темы Тема Количество практического занятия дисциплины часов 1 Распознавание типов формальных языков и грамматик. 1 Литература: [9], с. 8-60;

[15], с. 9-25;

[22];

[27];

[35];

[42];

[43].

2 Построение конечного автомата по регулярной граммати- 1 ке.

Литература: [9], с. 8-60;

[15], с. 9-25;

[22];

[27];

[35];

[42];

[43].

3 Минимизация конечных автоматов. Литература: [9], с. 8-60;

[15], с. 9-25;

[22];

[27];

[35];

[42];

[43].

4 Эквивалентные преобразования контекстно-свободных 1 грамматик.

Литература: [9], с. 8-60;

[15], с. 9-25;

[22];

[27];

[35];

[42];

[43].

5 Построение автомата с магазинной памятью по кон- 5 текстно-свободной грамматике.

Литература: [22], с. 15-72;

[27];

[34], с. 320-390;

[35];

[47].

6 Моделирование функционирования распознавателя для 5 LL(1)-грамматик.

Литература: [22], с. 15-72;

[27];

[34], с. 320-390;

[35];

[47].

7 Моделирование функционирования распознавателя для 5 грамматик простого предшествования.

Литература: [22], с. 15-72;

[27];

[34], с. 320-390;

[35];

[47].

2.2.1. Распознавание типов формальных языков и грамматик Задачами проведения настоящего занятия являются:

– закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;

– сформировать умения и навыки распознавания типов формальных языков и грамма тик по классификации Хомского, построения эквивалентных грамматик.

Основы теории Определение Р1.1. Алфавитом V называется конечное множество символов.

Определение Р1.2. Цепочкой в алфавите V называется любая конечная последова тельность символов этого алфавита.

Определение Р1.3. Цепочка, которая не содержит ни одного символа, называется пус той цепочкой и обозначается.

Определение Р1.4. Формальное определение цепочки символов в алфавите V:

1) – цепочка в алфавите V;

2) если – цепочка в алфавите V и а – символ этого алфавита, то а – цепочка в алфа вите V;

3) – цепочка в алфавите V тогда и только тогда, когда она является таковой в силу ут верждений 1) и 2).

Определение Р1.5. Длиной цепочки называется число составляющих ее символов (обозначается | |).

Обозначим через V * множество, содержащее все цепочки в алфавите V, включая пус тую цепочку, а через V + – множество, содержащее все цепочки в алфавите V, исключая пустую цепочку.

* Пример Р1.1. Пусть V = {1, 0}, тогда V = {, 0,1, 00, 01,10,11, 000,…}, а V + = {0,1, 00, 01, 10, 11, 000,…}.

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

G = ( VT,V N, P, S, ) (1.1) где VT – конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

V N – множество терминальных символов грамматики (обычно строчные латинские бу квы, цифры, и т.п.), VT V N = Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (VT V N ) + (VT V N ) * ;

элемент (, ) множества Р называется правилом вывода и записывается в виде (читается: «из цепочки выводится цепочка »);

S – начальный символ грамматики, S V N.

Для записи правил вывода с одинаковыми левыми частями вида 1, 2,…, n используется сокращенная форма записи 1 | 2 |…| n.

Пример Р1.2. Грамматика G1=({0, 1}, {A, S}, P1, S), где множество P1 состоит из пра вил вида: 1) S 0A1;

2) 0A 00A1;

3) A.

Определение Р1.7. Цепочка (VT V N ) * непосредственно выводима из цепочки (VT V N ) + в грамматике G = ( VT, V N, P, S, ) (обозначается: ), если = 1 2 и = 1 2, где * 1 2, (VT V N ) *, (VT V N ) + и правило вывода содержится во множестве Р.

Определение Р1.8. Цепочка (VT V N ) * выводима из цепочки (VT V N ) + в грамматике G = ( VT, V N, P, S, ) (обозначается *), если существует последовательность цепочек 0, 1,…, n (n 0) такая, что = 0 1 … n =.

Пример Р1.3. В грамматике G1 S *000111, т.к. существует вывод S 0A1 00A 000A111 000111.

Определение Р1.9. Языком, порожденным грамматикой G = ( VT, V N, P, S, ), называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамма * тики S c помощью правил множества Р, т.е. множество L(G) = { VT | S *}.

Пример Р1.4. Для грамматики G1 L( G1 )={ 0 n1n | n 0}.

Определение Р1.10. Цепочка (VT V N ) *, для которой существует вывод S *, называется сентенциальной формой в грамматике G = ( VT, V N, P, S, ).

Определение Р1.11. Грамматики G1 и G2 называются эквивалентными, если L( G1 ) = L( G2 ).

Пример Р1.5. Для грамматики G1 эквивалентной будет грамматика G2 = ({0, 1}, {S}, P2, S), где множество правил вывода P2 содержит правила вида S 0S1 | 01.

Классификация грамматик по Хомскому Тип 0. Грамматика G = ( VT, V N, P, S, ) называется грамматикой типа 0, если на ее прави ла вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

Тип 1. Грамматика G = ( VT, V N, P, S, ) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид, где (VT V N ) +, (VT V N ) * и || ||.

Тип 2. Грамматика G = ( VT, V N, P, S, ) называется контекстно-свободной грамматикой * (КС-грамматикой), если ее правила вывода имеют вид: A, где A V N и V Тип 3. Грамматика G = ( VT, V N, P, S, ) называется регулярной грамматикой (Р– грамматикой) выровненной вправо, если ее правила вывода имеют вид A aB | a, где a VT ;

A, B V N.

Грамматика G = ( VT, V N, P, S, ) называется регулярной грамматикой (Р–грамматикой) выровненной влево, если ее правила вывода имеют вид A Ba | a, где VT ;

A, B V N.

Определение Р1.12. Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.

Соотношение типов грамматик и языков представлено на рисунке 1.1.

Рис. Р1.1. Соотношение типов формальных языков и грамматик Р – регулярная грамматика;

КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;

Тип 0 – грамматика типа 0.

Пример Р1.6. Примеры различных типов формальных языков и грамматик по класси фикации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

2 а) Язык типа 0 L(G)={ a 2 b n | n 1 } определяется грамматикой с правилами вывода:

1) S aaCFD;

2) AD D;

3) F AFB | AB;

4) Cb bC;

5) AB bBA;

6) CB C;

7) Ab bA;

8) bCD.

б) Контекстно-зависимый язык L(G)={ a n b n c n | n 1} определяется грамматикой с пра вилами вывода:

1) S aSBC | abc ;

2) bC bc;

3) CB BC;

4) cC cc;

5) BB bb.

в) Контекстно-свободный язык L(G) = { (ab) n (bc) n | n 0} определяется грамматикой с правилами вывода:

1) S aQb | accb;

2) Q cSc.

г) Регулярный язык L(G)={ | {a, b}+ где нет двух рядом стоящих а} определяется грамматикой с правилами вывода:

1) S A | B;

2) A a | Ba;

3) B b | Bb | Ab.

Постановка задачи к практической работе № При выполнении лабораторной работы следует реализовать следующие действия:

1) составить грамматику, порождающую формальный язык, заданный в соответствии с вариантом;

2) определить тип формальной грамматики и языка по классификации Хомского;

3) разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского.

Варианты индивидуальных заданий представлены в табл. Р1.1.

Таблица Р1. Вариант Формальный язык 1 L(G ) = {a nb mc k | n, m, k 0} 2 L(G ) = {(ab) n (cb) m | n, m 0} 3 L(G ) = {0n (10) m | n, m 0} 4 L(G ) = {wcwcw | w {a, b}+ } 5 L(G ) = {c 2 n d n | n 0} 6 L(G ) = {l + l l | l {a, b}+ } 7 L(G ) = {(10) n 1 (01) n +1 | n 0} 8 L(G ) = {( ac) n | n 0, a {b, d }, c {+,}} 9 L(G ) = { (010) n | n 0} L(G ) = {a1a 2...an an...a2 a1 | ai {0, 1}} L(G ) = {a1a 2...an a1a2...an | ai {c, d }} 12 L(G ) = {ab, b | ai {+,}, b {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+ } 2.2.2. Построение конечного автомата по регулярной грамматике Задачами проведения настоящего занятия являются:

– закрепить понятия «регулярная грамматика», «недетерминированный и детерминиро ванный конечный автомат»;

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

Основы теории Распознавателем для регулярной грамматики является конечный автомат (КА).

Определение Р2.1. Детерминированным конечным автоматом (ДКА) называется пя терка объектов:

M = (Q, T, F, H, Z), (Р2.1) где Q – конечное множество состояний автомата;

T – конечное множество допустимых входных символов;

F – функция переходов, отображающая множество Q T во множество Q;

H – конечное множество начальных состояний автомата;

Z – множество заключительных состояний автомата, Z Q.

Определение Р2.2. Недетерминированным конечным автоматом (НКА) называется ко нечный автомат, в котором в качестве функции переходов используется отображение QT во множество всех подмножеств множества состояний автомата P(Q), т.е. функция переходов неоднозначна, так как текущей паре (q, t) соответствует множество очередных состояний ав томата qP(Q).

Способы представления функции переходов Командный способ. Каждую команду КА записывают в форме F(q, t) = p, где q, p Q, t T.

Табличный способ. Строки таблицы переходов соответствуют входным символам ав томата t T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции F(q, t).

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

Графический способ. Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автома та. Дуга ведет из состояния q в состояниe p и помечается списком всех символов t T, для которых F(q, t) = p. Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими ок ружностями.

Алгоритм Р2.1. Построение КА по регулярной грамматике Вход: регулярная грамматика G = ( VT, V N, P, S, ).

Выход: КА M = (Q, T, F, H, Z).

Шаг 1. Пополнить грамматику правилом A aN, где A VN, a VT и N – новый не терминал, для каждого правила вида A a, если в грамматике нет соответствующего ему правила A aB, где B VN.

Шаг 2. Начальный символ грамматики S принять за начальное состояние КА H. Из не терминалов образовать множество состояний автомата Q = VT {N}, а из терминалов – мно жество символов входного алфавита T = VT.

Шаг 3. Каждое правило A aB преобразовать в функцию переходов F(A, a) = B, где A, B VN, a VT.

Шаг 4. Во множество заключительных состояний включить все вершины, помеченные символами B VN из правил вида A aB, для которых имеются соответствующие правила A a, где A, B VN, a VT.

Шаг 5. Если в грамматике имеется правило S, где S – начальный символ граммати ки, то поместить S во множество заключительных состояний.

Шаг 6. Если получен НКА, то преобразовать его в ДКА.

Алгоритм Р2.2. Преобразование НКА в ДКА Вход: НКА M = (Q, T, F, H, Z).

Выход: ДКА M = (Q, T, F, H, Z).

Шаг 1. Пометить первый столбец таблицы переходов M ДКА начальным состоянием (множеством начальных состояний) НКА M.

Шаг 2. Заполняем очередной столбец таблицы переходов M, помеченный символами D, для этого определяем те состояния M, которые могут быть достигнуты из каждого симво ла строки D при каждом входном символе x. Поместить каждое найденное множество R (в том числе ) в соответствующие позиции столбца D таблицы M, т.е.:

F(D, x) ={s | sF(t, x) для некоторого tD}.

Шаг 3. Для каждого нового множества R (кроме ), полученного в столбце D таблицы переходов M, добавить новый столбец в таблицу, помеченный R.

Шаг 4. Если в таблице переходов КА M есть столбец с незаполненными позициями, то перейти к шагу 2.

Шаг 5. Во множество Z ДКА M включить каждое множество, помечающее столбец таблицы переходов M и содержащее qZ НКА M.

Шаг 6. Составить таблицу новых обозначений множеств состояний и определить ДКА M в этих обозначениях.

Пример Р2.1. Дана регулярная грамматика G = ({a, b},{S, A, B}, P, S) с правилами P:

1) S aB | aA;

2) B bB | a;

3) A aA| b. Построить по регулярной грамматике КА и преобразовать полученный автомат к детерминированному виду.

Решение задачи включает следующую последовательность действий.

1. Построим по регулярной грамматике КА.

1.1. Пополним грамматику правилами A bN и B aN, где N – новый нетерминал.

1.2. Начальное состояние конечного автомата H = S. Множество состояний автомата Q = VN = {S, A, B, N}, множество символов входного алфавита T = VT = {a, b}.

1.3. Значения сформированной функции переходов даны в табл. Р2.1.

Таблица Р2. Функция переходов автомата M F S A B N a A, B A N b N B 1.4. Множество заключительных состояний Z = {N}.

1.5. Для начального символа грамматики -правила отсутствуют.

Конечный автомат М – недетерминированный, граф НКА представлен на рис. 2.1 слева.

Рис. Р2.1. Граф НКА (слева) и ДКА (справа) для Р-грамматики 2. Построим по НКА M ДКА M.

2.1. Строим таблицу переходов для ДКА M (табл. Р2.2).

Таблица Р2. Построение функции переходов для ДКА M Шаг 1 2 3 4 5 6 F S A, B A, N B, N A N B a A, B A, N A N A N b B, N N B N B 2.2. Во множество заключительных состояний автомата M включим элементы Z = {(A, N), (B, N), N}.

2.3. Введем следующие новые обозначения состояний автомата M:

(A, B) = С, (A, N) = D, (B, N) = E.

2.4 Искомый ДКА определяется следующей пятеркой объектов:

Q = {S, A, B, C, D, E, N}, T = {a, b}, функция переходов задана табл. Р2.3, H ={S}, Z = {N, D, E}.

Граф полученного ДКА представлен на рис. Р2.1 справа.

Таблица Р2. Функция переходов для ДКА M F S A B C D E N a C A N D Q N b N B E N B Постановка задачи к практической работе № Разработать программное средство, реализующее следующие функции:

1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принад лежность к классу регулярных грамматик;

2) построение по заданной регулярной грамматике конечного автомата;

3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату;

4) вывод графа результирующего конечного автомата на экран.

Варианты индивидуального задания представлены в табл. Р2.4.

Таблица Р2. Варианты индивидуального задания к практической работе № Вариант Регулярная грамматика G = ({S, C, D}, {0,1}, P, S ), где P :

1) S 1C | 0 D;

2)C 0 D | 0 S | 1;

3) D 1C | 1S | 0.

G = ({S, A, B, C}, {a, b, c}, P, S ), где P :

1) S aA | bB | aC ;

2) A bA | bB | c;

3) B aA | cC | b;

4)C bB | bC | a.

G = ({K, L, M, N }, {a, b,+,, }, P, K ), где P :

1) K aL | bM ;

2) L N | M ;

3) M + N ;

4) N aL | bM |.

G = ({ X, Y, Z,W,V }, {0,1, ~, #,&}, P, X ), где P :

1) X 0Y | 1Z | ;

2)Y 0 Z |~ W |# ;

3) Z 1Y | 1W | 0V ;

4)W 0W | 1W |# ;

5)V & Z.

G = ({K, L, M, N, Q, P, R, S}, {0,1,*,$, /}, V, K ), где V :

1) K 1L | 0 N ;

2) L 0 M | 0 P | / Q;

3) N 1R | 1M | *S ;

4)Q 1P;

5) P *L | $;

6) M $;

7) S 0 R;

8) R / N | $.

G = ({E, A, B, C, D}, {0,1, a, b, c}, P, E ), где P :

1) E 0 A | ;

2) A aB | aD;

3) B bB | 1C | c;

4) D aD | 0C | c.

Вариант Регулярная грамматика G = ({ X, Y, Z,V,W }, {0,1, x, y, z}, P, X ), где P :

1) X yY | zZ ;

2)Y 1V ;

3) Z 0W | 0Y ;

4)V xZ | xW ;

5)W 1Y | 0.

G = ({S, A, B, C, D}, {a, b, c, d, }, P, S ), где P :

1) S aA | bB;

2) A cC |;

3)C cC | cA;

4) B dB |;

5) D dD | dB.

G = ({K, L, M, N, P}, {0,1,&,%, a, b}, C, K ), где C :

1) K 1M | ;

2) M 0 L | & N | & P;

3) L 1L | 0 L | % P;

4) N aN | bN | % P;

5) P 1P | aP | 0.

G = ({I, J, K, M, N }, {0,1, ~,!}, P, I ), где P :

1) I 0 J | 1K | 0 M ;

2) J ~ K | 0 M ;

3) K ~ M | 0 J | 0 N ;

4) M 1K |!;

5) N 0 I | 1I |!.

G = ({S, A, B, C, D, E}, {a, b, c, d, e,$, }, P, S ), где P :

1) S aA | bB | cC;

2) A dD;

3) B # D | $ E;

4) D dD | dB |;

5)C cE;

6) E eE | eB |.

G = ({ X, Y, Z,V }, {(, ), y, z, v}, P, X ), где P :

1) X (Y | ;

2)Y yY | zY | zZ ;

3) Z zZ | vZ | vV ;

4)V vV |) 2.2.3. Минимизация конечных автоматов Задачами проведения настоящего занятия являются:

– закрепить понятия «недостижимые состояния автомата», «эквивалентные состояния автомата», «минимальный конечный автомат»;

– сформировать умения и навыки минимизации детерминированного конечного авто мата.

Основы теории Конечный автомат может содержать лишние состояния двух типов: недостижимые и эквивалентные состояния.

Определение Р3.1. Два различных состояния q и q в конечном автомате M = (Q, T, F, H, Z) называются n-эквивалентными, n N{0}, если, находясь в одном их этих состояний и получив на вход любую цепочку символов :

V *T, ||n, автомат может перейти в одно и то же множество конечных состояний.

Определение Р3.2. Состояние q КА называется недостижимым, если к нему нет пути из начального состояния автомата.

Определение Р3.3. КА, не содержащий недостижимых и эквивалентных состояний, на зывается приведенным или минимальным КА.

Алгоритм Р3.1. Устранение недостижимых состояний КА Вход: КА M = (Q, T, F, H, Z).

Выход: КА M = (Q, T, F, H, Z).

Шаг 1. Поместить начальное состояние КА в список достижимых состояний Q g, т.е.

Qg 0 = H.

Шаг 2. Для новых элементов списка достижимых состояний пополнить список группой их состояний-приемников, отсутствующих в нем, т.е. Q g = Q g1 {p | g Q g1 F(g, t) = p} i i i Шаг 3. Повторить шаг 2, пока список достижимых состояний не перестанет меняться.

То есть, если Q g Q g1, то i = i + 1, иначе Q g = Q g i i i Шаг 4. Исключить из множества Q состояний КА все состояния, отсутствующие в спи ске Q g достижимых состояний, т.е. Q = Q Q g.

Шаг 5. Исключить недостижимые заключительные состояния и пары функции перехо дов, содержащие недостижимые состояния, т.е. Z = Z Q g, F = F {F(q, t) = p | q(Q Q g )}.

Пример Р3.1. Устранить недостижимые состояния КА M = (Q, T, F, H, Z), где Q = {A, B, C, D, E, F, G}, T = {a, b}, H = {A}, Z = {D, E} и функция переходов задана табл. Р3.1. Граф исходного КА М представлен на рис. Р3.1.

Таблица Р3. Функция переходов конечного автомата M F A B C D E F G a B C B D F b C D E E D G E Рис. Р3.1. Граф исходного конечного автомата М Последовательность устранения недостижимых состояний КА имеет вид:

Q0 = {A};

Q1 = {A, B, C};

Q2 = {A, B, C, D, E};

Q3 = {A, B, C, D, E};

т.к. Q2 = Q3, то Qд = {A, B, C, D, E}.

Qn = {F, G };

Q = {A, B, C, D, E};

Z= {D, E}.

Функция переходов автомата M представлена в табл. Р3.2.

Таблица Р3. Функция переходов автомата M F A B C D E a B C B b C D E E D Граф КА M после устранения недостижимых состояний представлен на рис. Р3.2.

Рис. Р3.2. Граф КА M после устранения недостижимых состояний Алгоритм Р3.2. Объединение эквивалентных состояний КА Вход: КА M = (Q, T, F, H, Z) без недостижимых состояний.

Выход: минимальный КА M = (Q, T, F, H, Z).

Шаг 1. На первом шаге строим нулевое разбиение R(0), состоящее из двух классов эк вивалентности: заключительные состояния КА – Z и не заключительные – Q – Z.

Шаг 2. На очередном шаге построения разбиения R(n) в классы эквивалентности вклю чить те состояния, которые по одинаковым входным символам переходят в n-1 эквивалент ные состояния, т.е. R(n) = { ri (n) :{ g ij Q: t T F( g ij,t) rj (n 1)} i, jN}.

Шаг 3. До тех пор, пока R(n) R(n – 1) полагаем n: = n + 1 и идем к шагу 2.

Шаг 4. Переобозначить оставшиеся неразбитые группы состояний и включить их в таб лицу новых обозначений состояний автомата.

Шаг 5. Определить эквивалентный КА M в новых обозначениях.

Пример Р3.2. Минимизировать конечный автомат из примера Р3.1.

Последовательность построения разбиений будет иметь вид:

R(0) = {{A, B, C}, {D, E}}, n = 0;

R(1) = {{A}, {B, C}, {D, E}}, n = 1;

R(2) = {{A}, {B, C}, {D, E}}, n = 2.

Т.к. R(1) = R(2), то искомое разбиение построено.

Переобозначим оставшиеся неразбитые группы состояний: X = {B, C}, Y = {D, E}.

Получим минимальный автомат M, где Q = {A, X, Y}, Z = {Y}.

Функция переходов автомата M представлена в табл. Р3.3.

Таблица Р3. Функция переходов автомата M F A X Y a X X b X Y Y Граф переходов конечного автомата после его минимизации показан на рис. Р3.3.

Рис. Р3.3. Граф минимального КА M Постановка задачи к практической работе № Разработать программное средство, реализующее следующие функции:

1) ввод исходного конечного автомата и вывод на экран его графа;

2) устранение недостижимых состояний конечного автомата;

3) исключение эквивалентных состояний конечного автомата;

4) вывод на экран графа минимального конечного автомата.

Разработать серию контрольных примеров для тестирования реализованных алгорит мов.

Варианты индивидуальных заданий к практической работе № 3 представлены на рис.

Р3.4.

2.2.4. Эквивалентные преобразования контекстно-свободных грамматик Задачами проведения настоящего занятия являются:

– закрепить понятия «эквивалентные грамматики», «приведенная КС-грамматика»;

– сформировать умения и навыки эквивалентных преобразований контекстно свободных грамматик.

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

Рассмотрим основные алгоритмы приведения КС-грамматик.

Перед всеми другими исследованиями и преобразованиями КС-грамматик выполняется проверка существования языка грамматики.

Алгоритм Р4.1. Проверка существования языка грамматики Вход: КС-грамматика G = ( VT, V N, P, S, ).

Выход: заключение о существовании или отсутствии языка грамматики.

Определим множество нетерминалов, порождающих терминальные строки N = {Z| Z V N, Z *x, x V *T }.


Шаг 1. Положить N 0 =.

Шаг 2. Вычислить N i = N i 1 {A| (A )P и ( N i 1 VT )*} Шаг 3. Если N i N i 1, то положить i = i + 1 и перейти к пункту 2, иначе считать N = Ni.

Если S N, то выдать сообщение о том, что язык грамматики существует, иначе сооб щить об отсутствии языка.

Рис. Р3.4. Варианты индивидуальных заданий к практической работе № Пример Р4.1. Дана грамматика G = ({0,1},{S, A, B}, P, S), где множество правил P:

1) S AB;

2) A 0A;

3) A 0;

4) B 1. Построим последовательность приближений множества N:

N 0 = ;

N 1 = {A, B};

N 2 = {S, A, B};

N 3 = {S, A, B}.

Т.к. N 2 = N 3, то N = {S, A, B}, следовательно, язык грамматики существует, потому что начальный символ S N.

Определение Р4.2. Бесполезными символами грамматики называют:

а) нетерминалы, не порождающие терминальных строк, т.е. множество символов {X | X V N,¬ (X *x), x V *T };

б) недостижимые нетерминалы, порождающие терминальные строки, т.е. множество символов {X | X V N,¬ (S * X ), (X *x);

, V * ;

x V *T };

в) недостижимые терминалы, т.е. множество символов {X | X VT,¬ (S * X),, V } * Алгоритм Р4.2. Устранение нетерминалов, не порождающих терминальных строк Вход: КС-грамматика G = ( VT,V N, P, S, ).

Выход: КС-грамматика G = ( VT, V N, P, S, ), такая, что L(G) = L(G) и для всех Z V N существуют выводы Z *x, где x V *T Шаг 1. Определить множество нетерминалов, порождающих терминальные строки, с помощью алгоритма 4.1.

Шаг 2. Вычислить VN = VN N, N B = VN VN, P = P PB, где PB P - это множест во правил, содержащих бесполезные нетерминалы X N B.

Пример Р4.2. Дана грамматика G = ({a, b, c}, {S, A, B, C}, P, S) с правилами P:

1) S ab;

2) S AC;

3) A AB;

4) B b;

5) C cb.

Преобразуем ее в эквивалентную грамматику G по алгоритму 4.2:

N 0 = ;

N 1 = {S, B, C};

N 2 = {S, B, C}.

Т.к. N 1 = N 2, то N = {S, B, C}. После удаления бесполезных нетерминалов и правил вы вода, получим грамматику G = ({a, b, c}, {S, B, C}, P, S) с правилами P : 1) S ab;

2) B b;

5) C cb.

Алгоритм Р4.3. Устранение недостижимых символов Вход: КС-грамматика G = ( VT, V N, P, S, ).

Выход: КС-грамматика G = ( VT, V N, P, S, ), такая, что L(G) = L(G) и для всех Z V существует вывод S *Z, где, (V)*.

Определим множество достижимых символов Z грамматики G, т.е. множество W = {Z | Z V, (S *Z);

, V*}.

Шаг 1. Положить W0 = S.

Шаг 2. Вычислить очередное приближение следующим образом:

Wi = Wi 1 {X | X V,( A X) P A Wi 1 ;

, V * }.

Шаг 3. Если Wi Wi 1, то положить i: = i + 1 и перейти к шагу 2, иначе считать W = Wi.

Шаг 4. Вычислить V N = VN W, VT = VT W, V B = V W, P = P PB, где PB P – это множество правил, содержащих недостижимые символы X V B.

Пример Р4.3. Дана грамматика G = ({a, b, c}, {S, B, C}, P, S) с правилами P:

1) S ab;

2) B b;

5) C cb.

Преобразуем ее в эквивалентную грамматику G по алгоритму 4.3:

W0 = {S};

W1 = {S, a, b};

W2 = {S, a, b}.

Т.к. W1 = W2, то W = {S, a, b}. Множество недостижимых символов V B ={B, C, c}. Тогда после удаления недостижимых символов, получим грамматику G = ({a, b},{S}, P, S) с пра вилом P: S ab.

Алгоритм 4.4. Устранение -правил Вход: КС-грамматика G = ( VT, V N, P, S, ).

Выход: Эквивалентная КС-грамматика G = ( VT, V N, P, S, ) без -правил для всех не терминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики.

Шаг 1. В исходной грамматике G найти -порождающие нетерминальные символы A VN, такие, что A *.

1.1. Положить N 0 = {A| (A ) P}.

1.2. Вычислить N i = N i 1 {B | (B ) P, N * i 1 } 1.3. Если N i N i 1, то положить i:= i + 1 и перейти к пункту 1.2, иначе считать N = N i.

Шаг 2. Из множества P правил исходной грамматики G перенести во множество P все правила, за исключением -правил, т.е. P = P {(A ) P для всех A VN }.

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

Шаг 4. Если S N, то P = P {S, S S}, VN = VN S, где V {S} = ;

иначе VN = VN, S = S.

Пример Р4.4. Дана грамматика G = ({0, 1},{S, A, B}, P, S) с правилами P:

1) S AB;

2) A 0A | ;

3) B 1B |. Преобразуем ее в эквивалентную грамматику по алгоритму 4.4.

Шаг 1. N 0 = {A, B};

N 1 = {S, A, B};

N 2 = {S, A, B}.

Т.к. N 1 = N 2, то искомое множество построено и N = {S, A, B}.

Шаг 2, 3. Множество P: 1) S AB | A| B;

2) A 0A| 0;

3) B 1B |1.

Шаг 4. Т.к. S N, то введем новый нетерминал С и пополним множество P правилом вида C S |. Результирующая грамматика будет иметь вид:

G = ({0, 1},{S, A, B, C}, P, C) с правилами P: 1) C S | ;

2) S AB | A| B;

3) A 0A | 0;

4) B 1B |1.

Алгоритм Р4.5. Устранение цепных правил Вход: КС-грамматика G = ( VT,V N, P, S, ).

Выход: Эквивалентная КС-грамматика G = ( VT, V N, P, S, ) без цепных правил, т.е. пра вил вида A B, где A, B V N.

Шаг 1. Для каждого нетерминала A вычислить множество выводимых из него нетерми налов, т.е. множество N A = ={B | A *B, где B V N }.

A 1.1. Положить N 0 = {A}.

1.2. Вычислить N i = N i 1 {C| BC P, B N i 1, C V N }.

A A A A A 1.3. Если N i N i 1, то положить i: = i + 1 и перейти к пункту 1.2, иначе считать A N A = Ni Шаг 2. Построить множество P так: если (B ) P не является цепным правилом ( V N ), то включить в P правило A для каждого A, такого, что B N A.

Пример Р4.5. Грамматика G = ({+, n}, {L, M, N}, P, L) с правилами P:

1) L M;

2) M N;

3) N N+ | n. Преобразуем ее в эквивалентную грамматику G по алгоритму 4.5.

Шаг 1.

L N 0 = {L};

L N1 = L, M};

L N 2 = L, M, N};

L N 3 = L, M, N}.

L L Т.к. N 2 = N 3, то N L = {L, M, N}.

M = {M};

N M = {M, N};

N M = {M, N}.

N M M = N 2, то N M = {M, N}.

Т.к. N N N 0 = {N};

N N 1 ={N}.

N N Т.к N 1 = N 0, то N N = {N}.

Шаг 2. Преобразовав правила вывода грамматики, получим грамматику G = ({+, n}, {L, M, N}, P, L) с правилами P: 1) L N+ | n;

2) M N+ | n;

3) N N+ | n.

Алгоритм Р4.6. Устранение левой факторизации правил Вход: КС-грамматика G = ( VT,V N, P, S, ).

Выход: Эквивалентная КС-грамматика G = ( VT, V N, P, S, ) без одинаковых префиксов в правых частях правил, определяющих нетерминалы.

Шаг 1. Записать все правила для нетерминала X, имеющие одинаковые префиксы V*, в виде одного правила с альтернативами:

X 1 | 2 | … | n ;

1, 2,…, n V*.

Шаг 2. Вынести за скобки влево префикс в каждой строке – альтернативе:

X ( 1 | 2 |…| n ).

Шаг 3. Обозначить новым нетерминалом Y выражение, оставшееся в скобках:

X Y, Y 1 | 2 |…| n.

Шаг 4. Пополнить множество нетерминалов новым нетерминалом Y и заменить прави ла, подвергшиеся факторизации, новыми правилами для X и Y.

Шаг 5. Повторить шаги 1-4 для всех нетерминалов грамматики, для которых это воз можно и необходимо.

Пример Р4.6. Дана грамматика G = ({k, l, m, n},{S}, P, S) с правилами P:

1) S kSl;

2) S kSm;

3) S n. Преобразуем ее в эквивалентную грамматику G по алгоритму 4.6:

Шаг 1. S kSl | kSm| n.

Шаг 2. S kS(l |m) | n.

Шаг 3,4. Пополнив множество нетерминалов новым нетерминалом С и заменив прави ла, подвергшиеся факторизации, получим грамматику G = ({k, l, m, n},{S, C}, P, S) с правилами P: 1) S kSC;

2) S n;

3) C l;

4) C m.

Алгоритм Р4.7. Устранение прямой левой рекурсии Вход: КС-грамматика G = ( VT,V N, P, S, ).

Выход: Эквивалентная КС-грамматика G = ( VT, V N, P, S, ) без прямой левой рекурсии, т.е. без правил вида A A, A V N, V*.

Шаг 1. Вывести из грамматики все правила для рекурсивного нетерминала X:

X X 1 | X 2 |…| X m (X V N ;

1, 2,… m ;

m V*).

X 1 | 2 |…| n ( 1, 2,… n ;

n V*) Шаг 2. Внести новый нетерминал Y так, чтобы он описывал любой «хвост» строки, по рождаемой рекурсивным нетерминалом X :

Y 1 Y| 2 Y|…| m Y Y 1 | 2 |…| m.

Шаг 3. Заменить в рекурсивном правиле для X правую часть, используя новый нетер минал и все нерекурсивные правила для X так, чтобы генерируемый язык не изменился:

X 1 Y| 2 Y|…| n Y X 1 | 2 |…| n Y 1 Y| 2 Y|…| m Y Y 1 | 2 |…| m.

Шаг 4. Пополнить множество нетерминалов грамматики новым нетерминалом Y. По полнить множество правил грамматики правилами, полученными на шаге 3.

Шаг 5. Повторить действия шагов 1-4 для всех рекурсивных нетерминалов грамматики, после чего полученные множества нетерминалов и правил принять в качестве V N и P.

Пример Р4.7. Дана грамматика G = ({a, b, c, d, z}, {S, A, B, C}, P, S) с правилами P:

1) S Aa;

2) A Bb;

3) B Cc | d;

4) C Ccbz | dbz.

После устранения прямой левой рекурсии получим эквивалентную грамматику G = ({a, b, c, d, z}, {S, A, B, C, Z}, P, S) с правилами P:

1) S Aa;

2) A Bb;

3) B Cc | d;

4) C dbzZ | dbz;

5) Z cbzZ | cbz.

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

1) организация ввода грамматики и проверка ее на принадлежность к классу КС грамматик;

2) проверка существования языка КС-грамматики;

3) реализация эквивалентных преобразований грамматики, направленных на удаление:

а) бесполезных символов;

б) недостижимых символов;

в) -правил;

г) цепных правил;

д) левой факторизации правил;


е) прямой левой рекурсии.

Варианты индивидуальных заданий представлены в табл. Р4.1.

Таблица Р4. Варианты индивидуальных заданий к практическим работам № 4 и № Вариант Контекстно-свободная грамматика G = ({S, A, B, D, E}, {a, b, c, e}, P, S ), где P :

1) S AB | ;

2) A Aa | S | a;

3) B bD | bS | b;

4) D ccD;

5) E eE | e.

G = ({E, T, F, G, H }, {+,,*, /, n, m, h}, P, E ), где P :

1) E T | E + T | E T | ;

2)T F | F * T | F / T | ;

3) F G | Fn | n;

4)G Gm;

5) H Hh | h.

G = ({S, R, T, X, Y }, {a, b, p, g, y}, P, S ), где P :

1) S R | T ;

2) R pX | paR | paT | ;

3)T Tg | g ;

4) X aXb;

5)Y aYa | y.

G = ({Q, A, B, C, D}, {a, b, c, d }, P, Q), где P :

1)Q acA | acB | ;

2) B A | Cb | ;

3) A Aa | Ab | a;

4)C dCc;

5) D dc.

5 G = ({R, T, F, G, K }, {m, i, j, k,, ~, }, P, R), где P :

1) R R ~ T | R T | ;

2)T F | Fi | Fj | Gk | ;

3)G GkG;

4) K Ki | Km | m.

G = ({S, X, Y, Z, K }, {x, y, z, k, #,$}, P, S ), где P :

1) S X | Y | Z ;

2) X x # X | x # Y | ;

3)Y Yy$ | Yz$ | $ | ;

4) Z Zz $;

5) K Kk $ | k $.

G = ({S, L, M, P, N }, {n, m, l, p, @, }, V, S ), где V :

1) S @ nL | @ mM | P;

2) L M | Ll | Lm | ;

3) M L | Mm | mm;

4) N pN @ | @;

5) P nmP.

G = ({ X, Y, Z, K, L}, {a, b, l, =,,,,, ¬}, V, X ), где V :

1) X Y | Y = Y | Y Y | Y Y | K ;

2)Y Y Z | Y Z | ;

3) Z ¬a | ¬b | ;

4) K ¬K ;

5) L l | a | b.

G = ({Q, A, B, C, D}, {0,1,}, P, Q), где P :

1)Q 01A | 01B | A;

2) A 0 B1 | B | 1 | ;

3) B BA0 | B1 | C | ;

4)C 0C11;

5) D D1 | 0 | 1.

Вариант Контекстно-свободная грамматика G = ({R, T,U,W,V }, {0,1,+,,*, /}, P, R), где P :

1) R T 1T | T1U | W | ;

2)T U | T 01 | T 10 | ;

3)U +U | +0 | +1;

4)W W W | W + W ;

5)V *0 | / 1.

G = ({S, R, T, F, E}, {a, b, k,{, [,}, ], }, P, S ), где P :

1) S {R | [ R;

2) R Ra} | Ra ] | a | T | F | ;

3) F {F } | bb;

4)T [T ];

5) E k.

12 G = ({Y, K, M, L, S}, {a, b,*, /, }, P, Y ), где P :

1)Y KS | KM ;

2) K K * | K / | S ;

3) S Sa / | Sb / | ;

4) M *M *;

5) L L | a.

2.2.5. Построение автомата с магазинной памятью по контекстно свободной грамматике Задачами проведения настоящего занятия являются:

– закрепить понятия «автомат с магазинной памятью (МПавтомат)», «расширенный МП-автомат», «конфигурация МП-автомата»;

«строка и язык, допускаемые МП-автоматом»;

– сформировать умения и навыки построения МП-автомата и расширенного МП автомата по КС-грамматике, разбора входной строки с помощью МП-автомата.

Основы теории КС-языки можно распознавать с помощью автомата с магазинной памятью (МП автомата).

Определение Р5.1. МП-автомат можно представить в виде семерки:

M = (Q, T, N, F, q 0, N 0, Z), (Р5.1) где Q – конечное множество состояний автомата;

T – конечный входной алфавит;

N – конечный магазинный алфавит;

F – магазинная функция, отображающая множество (Q (T {}) N) во множество всех подмножеств множества Q N*, т.е. F : (Q (T {}) N) P(Q N*);

q0 – начальное состояние автомата, q0 Q;

N 0 – начальный символ магазина, N 0 Т;

Z – множество заключительных состояний автомата, Z Q.

Определение Р5.2. Конфигурацией МП-автомата называется тройка вида:

(q,, ) (Q T* N*), (Р5.2) где q – текущее состояние автомата, q Q;

– часть входной строки, первый символ которой находится под входной головкой, T*;

– содержимое магазина, N*.

Общая схема МП-автомата представлена на рис. Р5.1.

Рис. Р5.1. Схема МП-автомата Алгоритм Р5.1. Функционирование МП-автомата Начальной конфигурацией МП-автомата является конфигурация ( q 0,, N 0 ).

Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции F(qQ, t(T {}), S N) является (q Q, N*), то записывается (q, t, S) |= (q,, ). При этом возможны следующие варианты.

1) Случай t T. Автомат находится в текущем состоянии q, читает входной символ t, имеет в вершине стека символ S. Он переходит в очередное состояние q, сдвигает входную головку на ячейку вправо и заменяет верхний символ S строкой магазинных символов. Ва риант = означает, что S удаляется из стека.

2) Случай t =. Отличается от первого случая тем, что входной символ t просто не при нимается во внимание, и входная головка не сдвигается. Такой шаг работы МП-автомата на зывается -шагом, который может выполняться даже после завершения чтения входной стро ки.

Заключительной конфигурацией МП-автомата является конфигурации (q,, ), где q Z.

Определение Р5.3. МП-автомат допускает входную стоку, если существует путь по конфигурациям ( q 0,, N 0 ) |= *(q,, ) для некоторых q Z и N*.

Определение Р5.4. Язык L, распознаваемый (принимаемый) МП- автоматом М опреде ляется как множество вида: L(M) = { | T* и ( q 0,, N 0 ) |= *(q,, ) для некоторых q Z и N*.

Определение Р5.5. МП-автомат с магазинной функцией F : (Q (T {}) N*) P(Q N*) называется расширенным МП-автоматом, т.е. автоматом, который может заменять це почку символов конечной длины в верхушке стека на другую цепочку символов конечной длины.

Существуют КС-языки, МП-автоматы и расширенные МП-автоматы, определяющие один и тот же язык.

Алгоритм Р5.2. Построение МП-автомата по КС-грамматике Построим МП-автомат, выполняющий левосторонний разбор. Данный автомат облада ет только одним состоянием и принимает входную строку опустошением магазина. Стек ис пользуется для размещения текущей сентенции, первоначально это начальный символ грам матики. Очередная сентенция получается заменой верхнего нетерминала стека.

Вход: КС-грамматика G = ( VT,V N, P, S, ).

Выход: МП-автомат M = (Q, T, N, F, q 0, n0, Z) такой, что L(M) = L(G).

Шаг 1. Положить Q = {q}, q0 = q, Z =, N = VT VN, T = VT, N 0 = S.

Шаг 2. Для каждого правила вида (А ) P, где V*, сформировать магазинную функцию вида F(q,, A) = (q, ). Эти функции предписывают замещать нетерминал в верши не стека по правилу грамматики.

Шаг 3. Для каждого t VT сформировать магазинную функцию вида F(q, t, t) = (q, ), которая выталкивает из стека символ, совпадающий с входным, и перемещает читающую головку. Эти функции обеспечивают опустошение стека.

Пример Р5.1. Дана КС-грамматика: G({+, (, ), a}, {S, A}, {SS+A | A, A(S) | a}, {S}).

Последовательность построения МП-автомата будет иметь вид.

1) Q = {q}, q0 = q, T = {+, (, ), a }, N = {+, (, ), a, S, A}, N 0 = S, Z =.

2) F(q,, S) = (q, S+A), F(q,, S) = (q, A), F(q,, A) = (q, (S));

F(q,, A) = (q, a).

3) F(q, t, t) = (q, ) для каждого t {+, (, ), a}.

Распознавание строки (а) построенным МП-автоматом представлено в табл. Р5.1. По лученный МП-автомат является недетерминированным.

Таблица Р5. Распознавание МП-автоматом строки (а) Номер конфи- Текущее со- Входная Содержимое гурации стояние строка магазина 1 (a) q S 2 (a) q A 3 (a) (S) q 4 a) S) q 5 a) A) q 6 a) a) q 7 ) ) q 8 q Алгоритм Р5.3. Построение расширенного МП-автомата по КС-грамматике Построим МП-автомат, выполняющий правосторонний разбор. Данный автомат имеет единственное текущее состояние и одно заключительное состояние, в котором стек пуст.

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

Вход: КС-грамматика G = ( VT,V N, P, S, S).

Выход: расширенный МП-автомат M = (Q, T, N, F, q 0, n0, Z) такой, что L(M) = L(G).

Шаг 1. Положить Q = {q, r}, q 0 = q, Z = {r}, N = VT VN {#}, T = VT, N 0 = #.

Шаг 2. Для каждого правила вида (A ) P, где V*, сформировать магазинную функцию вида F(q,, ) = (q, A), предписывающую заменять правую часть правила в верши не стека нетерминалом из левой части, независимо от текущего символа входной строки.

Шаг 3. Для каждого терминала t T сформировать магазинную функцию вида F(q, t, ) = (q, t), которая помещает символ входной строки в вершину стека, если там нет правой час ти правила, и перемещает читающую головку.

Шаг 4. Предусмотреть магазинную функцию для перевода автомата в заключительное состояние F(q,, # S) = (r, ).

Пример Р5.2. Для грамматики из примера Р5.1 построить расширенный МП-автомат.

Последовательность построения МП-автомата будет иметь вид.

1) Q = {q, r}, q 0 = q, T = {+, (, ), a}, N = {+, (, ), a, S, A}, N 0 = #, Z = r.

2) F(q,, S+A) = (q, S), F(q,, A) = (q, S), F(q,, (S)) = (q, A), F(q,, a) = (q, A).

3) F(q, t, ) = (q, t) для каждого t {+, (, ), a}.

4) F(q,, #S) = (r, ).

Распознавание строки (а) расширенным МП-автоматом представлено в табл. Р5.2.

Полученный МП-автомат является детерминированным.

Таблица Р5. Распознавание расширенным МП-автоматом строки (а) Номер конфи- Текущее со- Входная Содержимое гурации стояние строка магазина 1 a) q # 2 a) #( q 3 ) #(a q 4 ) #(A q 5 ) #(S q 6 #(S) q 7 q #A 8 q #S 9 r Постановка задачи к практической работе № Разработать программное средство, реализующее следующие функции:

а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;

б) построение МП-автомата по КС-грамматике;

в) построение расширенного МП-автомата по КС-грамматике.

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

а) входная строка принадлежит языку исходной КС-грамматики и допускается МП автоматом;

б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.

Индивидуальные варианты заданий представлены в табл. Р4.1.

2.2.6. Моделирование функционирования распознавателя для LL(1) грамматик Задачами проведения настоящего занятия являются:

– закрепить понятие «LL(k) –грамматика», необходимые и достаточные условия LL(k) – грамматики;

– сформировать умения и навыки построения множеств FIRST(k, ) и FOLLOW(k, ), распознавателя для LL(1)-грамматик.

Основы теории Определение Р6.1. КС-грамматика обладает свойством LL(k) для некоторого k 0, ес ли на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего положения считывающей головки во входной строке.

Определение Р6.2. КС-грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k 0.

В основе распознавателя LL(k)-грамматик лежит левосторонний разбор строки языка.

Исходной сентенциальной формой является начальный символ грамматики, а целевой – за данная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Отсюда и произошла аббревиатура LL(k): первая «L» (от слова «left») означает левосторонний ввод исходной цепочки символов, вторая «L»

– левосторонний вывод в процессе работы распознавателя.

Определение Р6.3. Для построения распознавателей для LL(k)-грамматик используют ся два множества:

– FIRST(k, ) – множество терминальных цепочек, выводимых из цепочки ( VT VN )*, укороченных до k символов;

– FOLLOW(k, A) – множество укороченных до k символов терминальных цепочек, ко торые могут следовать непосредственно за A VN в цепочках вывода.

Формально эти множества можно определить следующим образом:

– FIRST(k, ) = { V *T | вывод * и || k или вывод *x и || = k;

x, ( VT VN )*, k 0};

– FOLLOW(k, A) = { V *T | вывод S *A и FIRST(k, );

, V*, A VN, k 0}.

Теорема Р6.1. Необходимое и достаточное условие LL(1)-грамматики Для того чтобы грамматика G( VT, V N, P, S, ) была LL(1)-грамматикой необходимо и достаточно, чтобы для каждого символа A VN, у которого в грамматике существует более одного правила вида А 1 | 2 |…| n, выполнялось требование:

FIRST(1, i FOLLOW(1, A)) FIRST(1, j FOLLOW(1, A)) =, i j, 0 I n, 0 j n.

Т.е. если для символа А отсутствует правило вида А, то все множества FIRST(1, 1 ), FIRST(1, 2 ),…, FIRST(1, n ) должны попарно не пересекаться, если же присутствует правило А, то они не должны также пересекаться с множеством FOLLOW(1, A).

Для построения распознавателей для LL(1)-грамматик необходимо построить множест ва FIRST(1, x) и FOLLOW(1, A). Причем, если строка х будет начинаться с терминального символа а, то FIRST(1, x) = a, и если она будет начинаться с нетерминального символа А, то FIRST(1, x) = FIRST(1, A). Следовательно, достаточно рассмотреть алгоритмы построения множеств FIRST(1, A) и FOLLOW(1, A) для каждого нетерминального символа А.

Алгоритм Р6.1. Построение множества FIRST(1, A) Для выполнения алгоритма необходимо предварительно преобразовать исходную грамматику G в грамматику G, не содержащую -правил (см. лабораторную работу № 4).

Алгоритм построения множества FIRST(1, A) использует грамматику G.

Шаг 1. Первоначально внести во множество первых символов для каждого нетерми нального символа А все символы, стоящие в начале правых частей правил для этого нетер минала, т.е. А VN FIRST(1, A) = {X | AX P, X ( VT VN ), ( VT VN )*}.

Шаг 2. Для всех А VN положить:

FIRSTi+1 (1, A) = FIRSTi (1, A) FIRSTi (1, B), В(FIRST(1, A)VN).

Шаг 3. Если существует А VN, такой что FIRSTi +1 (1, A) FIRSTi (1, A), то присвоить i = i + 1 и вернуться к шагу 2, иначе перейти к шагу 4.

Шаг 4. Исключить из построенных множеств все нетерминальные символы, т.е.

А VN FIRST(1, A) = FIRSTi (1, A) \ N.

Алгоритм Р6.2. Построение множества FOLLOW(1, A) Алгоритм основан на использовании правил вывода грамматики G.

Шаг 1. Первоначально внести во множество последующих символов для каждого не терминального символа А все символы, которые в правых частях правил вывода встречаются непосредственно за символом А, т.е.

А VN FOLLOW0 (1, A) = {X | B AX P, B VN, X ( VT VN ),, ( VT VN )*}.

Шаг 2. Внести пустую строку во множество FOLLOW(1, S), т.е.

FOLLOW(1, S) = FOLLOW(1, S){}.

Шаг 3. Для всех А VN вычислить:

FOLLOWi (1, A)= FOLLOWi (1, A) FIRST(1, B), B ( FOLLOWi (1, A) VN ).

Шаг 4. Для всех А VN положить:

FOLLOWi (1, A)= FOLLOWi (1, A) FOLLOWi (1, B), B ( FOLLOWi (1, A) VN ), если правило B.

Шаг 5. Для всех А VN определить:

FOLLOWi+1 (1, A) = FOLLOWi (1, A) FOLLOWi (1, B), для всех нетерминальных символов B VN, имеющих правило вида B A, ( VT VN )*.

Шаг 6. Если существует А VN такой, что FOLLOWi+1 (1, A) FOLLOWi (1, A), то по ложить i: = i + 1 и вернуться к шагу 3, иначе перейти к шагу 7.

Шаг 7. Исключить из построенных множеств все нетерминальные символы, т.е.

А VN FOLLOW(1, A) = FOLLOWi (1, A)\ N.

Алгоритм Р6.3. Функционирование распознавателя цепочек для LL(1)-грамматик Шаг 1. Помещаем в стек начальный символ грамматики S, а во входной буфер исход ную цепочку символов.

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

– если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А х при условии, что а FIRST(1, x), т.е. извлекаем из стека символ А и заносим в стек строку х, не меняя со держимого входного буфера;

– если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А при условии, что а FOLLOW(1, A), т.е. извлекаем из стека символ А и заносим в стек строку, не меняя содержимого входного буфера;

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

– если содержимое стека и входного буфера пусто, то исходная строка прочитана пол ностью, и разбор завершен удачно;

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

Пример Р6.1. Дана грамматика G ({S, T, R}, {+, –, (, ), a, b}, P, S), с правилами P:

1) STR;

2) R | +TR | - TR;

3) T(S) | a | b.

2) Построить распознаватель для строки (a +(b – a)) языка грамматики G.

Этап 1. Преобразуем грамматику G в грамматику G, не содержащую -правил:

N 0 = {R};

N 1 = {R}, т.к. N 0 = N1, то во множество P войдут правила:

1) S TR | T;

2) R +TR | +T | –TR | –T;

3) T (S) | a | b.

Этап 2. Построение множеств FIRST(1, A) для каждого нетерминала А представлено в табл. Р6.1.

Таблица Р6. Построение множеств FIRST(1, A) FIRSTi(1, A) 0 1 2 FIRST (1, A) T, (, a, b T, (, a, b (, a, b S T +, – +, – +, – +, – R (, a, b (, a, b (, a, b (, a, b T Этап 3. Построение множеств FOLLOW(1, A) для каждого нетерминала А представлено в табл. Р6.2.

Таблица Р6. Построение множеств FOLLOW(1, A) Шаг Нетерминалы FOLLOWi(1, A) FOLLOWi(1, A) FOLLOWi(1, A) 0 ) ), ), S R R, +, – R, +, – T R 1 ), ), ), S ), ), ), R R, + – R, + – R, + –, ), T 2 ), ), ), S ), ), ), R R, + –, ), R, + –, ), R, + –, ), T FOLLOW(1, S) ), FOLLOW(1, R) ), FOLLOW(1, T) +, –, ), Этап 4. Множества FIRST(1, A) и FOLLOW(1, A) для каждого нетерминала А сведены в табл. Р6.3.

Таблица Р6. Множества FIRST(1, A) и FOLLOW(1, A) FIRST(1, A) FOLLOW(1, A) A (, a, b ), S +, – ), R (, a, b +, –, ), T Грамматика G является LL(1)-грамматикой, т. к. для каждого нетерминала А, имеющего альтернативные выводы, множества FIRST(1, A) попарно не пересекаются, а для нетерминала R они также не пересекаются со множеством FOLLOW(1, R).

Шаг 5. Разбор строки (a+(b-a)) для грамматики G показан в табл. Р6.4.

Таблица Р6. Разбор строки (a + (b – a)) для грамматики G Стек Входной Действие буфер (a + (b a)) S TR, т.к. ( FIRST (1, TR) S свертка (a + (b a)) T (S ), т.к. ( FIRST (1, ( S )) TR свертка (a + (b a)) (S)R выброс (a + (b a)) S TR, т.к. а FIRST (1, TR) S)R свертка (a + (b a)) Т а, т.к. а FIRST (1, а ) TR)R свертка (a + (b a)) aR)R выброс + (b a )) R +TR, т.к. + FIRST (1, TR) R)R свертка + (b a )) +TR)R выброс (b a)) T (S ), т.к. ( FIRST (1( S )) TR)R свертка (b a)) (S)R)R выброс b a )) S TR, т.к. b FIRST (1, TR ) S)R)R свертка b a )) Т b, т.к. b FIRST (1, b) TR)R)R свертка Стек Входной Действие буфер b a )) bR)R)R выброс a)) свертка R TR, т.к. FIRST (1,TR ) R)R)R a)) –TR)R)R выброс свертка T a, т.к. a FIRST (1, a ) a)) TR)R)R aR)R)R a)) выброс свертка R, т.к. FOLLOW (1, R) R)R)R )) )R)R )) выброс свертка R, т.к. FOLLOW (1, R) R)R ) )R ) выброс свертка R, т.к. FOLLOW (1, R) R строка принята полностью Шаг 6. Получили следующую цепочку вывода:

STR(S)R(TR)R (aR)R (a+TR)R (a+(S)R)R (a+(TR)R)R (a+(bR)R)R (a+(b-TR)R)R (a+(b-aR)R)R (a+(b-a)R)R (a+(b-a))R (a+(b-a)).

Нисходящее дерево разбора цепочки представлено на рис. Р6.1.

Постановка задачи к практической работе № Разработать программное средство, автоматизирующее процесс разбора цепочек для LL(1)-грамматик. Программное средство должно выполнять следующие функции:

1) реализация ввода произвольной КС-грамматики;



Pages:     | 1 |   ...   | 2 | 3 || 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.