Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

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

Ярким примером эффективности комбинаторного подхода является теория бинома Ньютона. Все красивые результаты — различные соотношения между биномиальными коэффициентами — имеют простое комбинаторное истолкование.

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

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

Если задана нумерация множества , то применяют следующие обозначения:

Теорема – правило суммы. Пусть и – конечные непересекающиеся множества, то есть , тогда

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

Зафиксируем , нумерации и соответственно и рассмотрим отображение

,

заданное правилом:

Очевидно, – биективное отображение, тогда на основании основного принципа комбинаторики получаем

.

Теорема (следствие из предыдущей). Пусть и – конечные множества, тогда .

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

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

. (*)

Очевидно, и множества , тогда из равенства правила суммы получаем

. (**)

Подставляя выражение для из (**) в (*), получаем

.

Теорема – правило включения-исключения.

Пусть – конечные множества, тогда

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

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

Докажем формулу включения-исключения по индукции.

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

Здесь мы воспользовались равенствами

Теорема – правило суммы непересекающихся множеств.

Если – конечное попарно не пересекающиеся множества (т.е. , ), то

.

Ясно, что это тривиальное следствие из предыдущей теоремы.

59.Декартово произведение множеств.

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

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

пусть

Теорема.

Если и – конечные множества, то – конечное множество и .

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

Ясно, что в случае, когда одно из множеств , пусто, то и пусто и тривиально выполнено. Рассмотрим случай, когда и – непустые множества. Зафиксируем в нумерацию

.

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

(*).

Рассмотрим отображение , действующее по правилу

.

Ясно, что – биективное отображение, тогда по основному принципу комбинаторики получаем

(**).

Подставляя (**) в (*), получим:

.

60.Множество степень.

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

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

Теорема.

Если – конечное множество, то

.

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

Ясно, что эта теорема является следствием из предыдущей теоремы.

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

Пусть и – непустые множества. Обозначим через множество отображений, действующих из в , то есть

.

Множество называется множеством степень.

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

Лемма 1. Пусть и – конечные непустые множества и ,

тогда

.

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

Зафиксируем в и нумерации – , .

Занумеруем элементы множества условием:

.

Ясно, что нумерующий отрезок – .

Лемма 2. Пусть и – конечные непустые множества и , , тогда

.

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

Зафиксируем в и нумерации, выбрав такую нумерацию множества , при которой .

Множество представим в виде объединения попарно непересекающихся множеств , отнеся ко множеству , если

.

По правилу суммы получаем:

. (*)

Рассмотрим одно из множеств . Каждое отображение однозначно определяется своим ограничением (сужением) на множество . (Стрелочная диаграмма любого отображения , содержит стрелку, ведущую из в )

Стрелки указанные пунктиром – ограничение на .

Ясно, что . (**)

Подставляя из (**) в (*), получаем

.

Теорема. Пусть , – конечные непустые множества, тогда –конечное множество и

.

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

Проведём доказательство методом математической индукции, взяв в качестве параметра индукции число элементов во множестве .

1-й шаг (случай |x|=1). Применяя лемму 1, имеем:

.

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

.

Множество содержит элементов и к применимо предложение индукции, тогда

.

Индуктивный переход, а значит, и вся теорема доказаны.

61.Примеры задач и упражнений.

1. Практическое занятие №1. Разработка синтаксических анализаторов для регулярных языков.

62.Общие указания к выполнению практической работы.

Практические работы выполняются с использованием персональных компьютеров. Указания по технике безопасности совпадают с требованиями, предъявляемыми к пользователю ЭВМ. Другие опасные факторы отсутствуют.

63.Цель работы

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

64.Постановка задачи

7.03.1. Описание грамматики.

Рассмотрим регулярное выражение (221b)* (b21)* (22)*. Это выражение порождает предложения языка:

L = {(221b)^m (b21)ⁿ (22)^p: m, n, p > 0}.

Языку L соответствует регулярная порождающая грамматика: G = ({1, 2, b}, (А, В, С, D, Е, F, К, L, M, S}, P, S), где Р={S→2A; А→2В; В→1C; С→bS; S→ε; S→2D; D→2Е; Е→IF; F→bD; F→ε; F→2K; K→2L; L→2M; M→2L; L→ε; В→ε; В→2K} — порождающие правила; {1, 2, b} — множество терминальных символов; {А, В, С, D, Е, F, К, L, M, S} — множество нетерминальных символов; S — аксиома; ε — пустая строка.

Для каждой регулярной грамматики существует детерминированный конечный автомат. Грамматике G соответствует автомат:

M = ({А, В, С, S, D, Е, F, К, L, М), {1, 2, b}, d, {S}, (S, В, F, L}), где {А, В, С, S, D, Е, F, К, L, М} — конечное множество состояний; {1, 2, Ь} — конечный входной алфавит; d — множество переходов:

{d(S, 2) = A; d(S, b) = D; d(F, 2) = K;

d(A,2) = B; d(D,2) = E; d(B,2) = K;

d(B, 1) = C; d(E,l) = F; d(K,2) = L;

d(C, b) = S; d(F, b) = D; d(L, 2) = M;

d(M,2) = L};

S - начальное состояние (S {A, B, C, S, D, E, F, K, L, M});

{S, B, F, L} - множество последних состояний

({S, В, F, L} {A, B, C, S, D, E, F, K, L, M}).

Множество переходов d может быть эквивалентно представлено таблицей переходов:

Здесь  — пустое множество.

Здесь состояния S, В, F, L являются последними.

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

8.2. Формулировка задания.

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

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

Написать и проверить работоспособность соответствующего синтаксического анализатора.

Краткие сведения из теории

Конечный автомат — это устройство для распознавания строк какого-либо языка. Конечный автомат — это пятерка М = (К, , , S, F),

где K — конечное множество состояний;

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

 — множество переходов;

S — начальное состояние (S  К);

F — множество последних состояний (F  К).

По мере считывания каждой литеры строки автоматом контроль передается от состояния к состоянию в соответствии с заданным множеством переходов.

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

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

Пример.

Рассмотрим автомат M0 = (К, , , S, F),

где К ={А, В}, S = {0, 1}, S = {A}, F = {A},

 = { (А, 0) = А,  (А, 1) = В,  (В, 0) = В,  (В, 1) = А}.

Эти переходы означают, что "при чтении 0 в состоянии А управление передается в состояние А и т. д.

При чтении строки 0110010111 управление последовательно передается в следующем порядке через состояния А, А, В, А, А, А, В, В, А, В, А.

Так как А — есть последнее состояние, строка принимается конечным автоматом.

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

Характеристики

Список файлов лекций