lekcii_dm
.pdf
различного размещения и при симметричном отображении (их 2).
Следовательно 2n!n .
Пример 7
Из колоды в 52 карты вынули 10 карт. В скольких случаях среди этих карт окажется а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов; г) ровно два туза.
Решение.
а) Существует С5210 способов вынуть 10 карт из 52. При этом в С4810
случаях в этой выборке не окажется ни одного туза. Следовательно С5210 С4810
б) С41С489 в) С5210 – С4810 – С41 С489 г) С42С488
Пример 8
Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом.
Решение
Выбрать места для мужчин и женщин можно двумя способами. После этого рассадить мужчин на выбранные места можно n! способами. На остальных местах n! способами можно посадить женщин. Всего 2(n!)2 способов.
Пример 10
Сколькими способами можно составить 3 пары из n шахматистов?
Решение
211
Выбираем 6 шахматистов Сn6 способами. В каждой из этих выборок рассмотрим количество перестановок их 6!. Считая, что в первой паре элементы с 1 – ого и 2 – го места перестановки и т.д. Но при этом несущественен порядок в каждой паре 23 и порядок пар 3!. Следовательно,
количество перестановок равно 6!/ (23 3!). Итого Сn66! 23 3!
7.04.Задачи для самостоятельного решения.
1.Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой?
2.Сколько словарей нужно издать, чтобы переводить с любого из 5 языков на любой другой?
3.Есть пятиразрядный цифровой замок, каждый диск которого содержит цифры от0 до 5. Сколько комбинаций таких цифр?
4.Сколькими способами можно упорядочить множество цифр от 1 до 2n так, чтобы все четные числа стояли на четных местах.
5.Сколькими способами можно упорядочить множество цифр от 1 до n так, чтобы числа 1,2,3 стояли рядом и в порядке возрастания.
6.Какое количество различных символов можно передать не более чем 5 знаками «.» и «-».
7.Автомобильные номера состоят из 3 букв и 4 цифр. Найти количество возможных номеров, если используются 32 букв русского алфавита.
8.Сколько машинных слов можно составить из букв слова КОЛОКОЛ.
9.Сколько машинных слов можно составить из букв слова ВОДОРОД.
212
10.Сколькими способами 9 одинаковых конфет можно разложить по 5 пакетам, если ни один из пакетов не должен быть пустым. Тот же вопрос, но пакеты могут быть пустыми.
Глава 8. Основная часть: практическая работа студентов
Практическое занятие №1. Разработка синтаксических анализаторов для регулярных языков.
8.01. Общие указания к выполнению практической работы.
Практические работы выполняются с использованием персональных компьютеров. Указания по технике безопасности совпадают с требованиями, предъявляемыми к пользователю ЭВМ. Другие опасные факторы отсутствуют.
8.02. Цель работы
Написание, отладка и проверка работоспособности синтаксического анализатора на основе графа детерминированного конечного автомата, соответствующего заданному регулярному выражению, порождающему конкретный язык.
8.03.Постановка задачи
8.03.1.Описание грамматики.
Рассмотрим регулярное выражение (221b)* (b21)* (22)*. Это выражение порождает предложения языка:
L = {(221b)m (b21)n (22)p: m, n, p > 0}.
213
Языку 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 может быть эквивалентно представлено таблицей переходов:
Здесь — пустое множество.
214
Здесь состояния S, В, F, L являются последними.
Множество переходов также может быть представлено графически с помощью графа переходов из одного состояния детерминированного конечного автомата в другое. Для рассматриваемого варианта граф имеет следующий вид:
8.03.2. Формулировка задания.
Для заданного варианта регулярного выражения написать регулярную грамматику.
Представить детерминированный конечный автомат, соответствующий регулярной грамматике.
Написать и проверить работоспособность соответствующего синтаксического анализатора.
Краткие сведения из теории Конечный автомат — это устройство для распознавания строк какого-
либо языка. Конечный автомат — это пятерка М = (К, , , S, F), где K — конечное множество состояний;
— конечный входной алфавит;— множество переходов;
S — начальное состояние (S К);
F — множество последних состояний (F К).
По мере считывания каждой литеры строки автоматом контроль передается от состояния к состоянию в соответствии с заданным множеством переходов.
215
Определение.
Если после считывания последней литеры строки автомат будет находиться в одном из последних состояний, то о строке говорят, что она принадлежит языку, принимаемому автоматом. В противном случае строка не принадлежит языку, принимаемому автоматом.
Пример.
Рассмотрим автомат M0 = (К, , , S, F),
где К ={А, В}, S = {0, 1}, S = {A}, F = {A},
= { (А, 0) = А, (А, 1) = В, (В, 0) = В, (В, 1) = А}.
Эти переходы означают, что "при чтении 0 в состоянии А управление передается в состояние А и т. д.
При чтении строки 0110010111 управление последовательно передается в следующем порядке через состояния А, А, В, А, А, А, В, В, А, В, А.
Так как А — есть последнее состояние, строка принимается конечным автоматом.
Однако, при чтении строки 00111 автомат проходит через состояния А, А, А, В, А, В. В не является последним состоянием строка 00111 не принимается, т.е. она не принадлежит языку, принимаемому этим автомат.
В связи с тем, что нули не влияют на состояние автомата, каждая единица изменяет его состояние с А на В и с В на А, и начальное состояние является тем же, что и последнее состояние. Язык, принимаемый автоматом, состоит из тех строк, которые содержат четное число единиц.
Переходы можно представить также с помощью таблицы и схематически:
216
Определение.
Автомат называется детерминированным, если в каждом элементе таблицы переходов содержится одно состояние. В недетерминированном конечном автомате это положение не выдерживается.
Следовательно, автомат M0 — детерминированный.
8.04. Последовательность выполнения.
Для выполнения лабораторной работы требуется умение писать программы на алгоритмическом языке, а также начальные знания по порождающим грамматикам.
Таким образом, последовательность выполнения лабораторной работы следующая:
1.Ознакомится с теорией регулярных грамматик.
2.В соответствии с заданным регулярным выражением написать регулярную грамматику.
3.Записать соответствующий детерминированный конечный автомат с указанием таблицы переходов.
4.Написать и отладить на компьютере синтаксический анализатор, распознающий выражения регулярного языка.
5.Привести контрольную распечатку.
6.Оформить отчет.
Работа считается выполненной только после оформления отчета,
защиты и подписи преподавателя.
217
8.05. Методический пример.
Программа "grammatika", представляющая синтаксический анализатор, соответствующий детерминированному конечному автомату М, имеет следующий вид:
program grammatika; uses crt;
type perehod = record old, term, new: char; end;
var sost:array [1 .. 13] of perehod; stroka: string [255];
sim, neterm: string [1]; dlina, n, i: integer; ok: boolean;
begin { блок определения таблицы переходов }
sost[1].old :='S'; |
sost[1].term :='2'; |
sost[1].new := 'A'; |
sost[2].old :='A'; |
sost[2].term :='2'; |
sost[2].new := 'B'; |
sost[3].old :='B'; |
sost[3].term :='1’; |
sost[3].new := 'C'; |
sost[4].old := 'C'; |
sost[4].term := 'b'; |
sost[4].new := 'S'; |
sost[5].old := 'S'; |
sost[5].term := 'b'; |
sost[5].new := 'D'; |
sost[6].old :='D'; |
sost[6].term :='2'; |
sost[6].new :='E'; |
sost[7].old :='E'; |
sost[7] .term := '1'; |
sost[7].new :='F'; |
sost[8].old := 'F'; |
sost[8].term := 'b'; |
sost[8].new := 'D'; |
sost[9].old := 'F'; |
sost[9].term := '2'; |
sost[9].new := 'K'; |
sost[10].old:='B'; |
sost[10].term :='2'; |
sost[10].new := 'K'; |
sost[11].old := 'K'; |
sost[11].term := '2'; |
sost[11].new := 'L'; |
sost[12].old := 'L'; |
sost[12].term := '2'; |
sost[12].new := 'M'; |
sost[13].old := 'M'; |
sost[13].term := '2'; |
sost[13].new := 'L'; |
clrscr; |
|
|
218
{ блок основной программы } while TRUE do begin
writeln ('Введите строку символов’); readln (stroka);
dlina := length (stroka); n:=0;
ok :=' TRUE; neterm := 'S';
while ok and (n < dlina) do begin i := 0;
n:=n+ 1
sim := copy (stroka, n, 1); ok := FALSE;
repeat i:=i+l;
if ((sost [i].old = neterm) and (sost [i].term = sim)) then begin
ok := TRUE; neterm := sost[i].new; end;
until ( ok or (i = 13)); end;
if ((neterm = 'S') or (neterm = 'B') or (neterm = 'F') or (neterm = 'L') and ok then writeln ('Данная строка принадлежит языку')
else writeln ('Данная строка не принадлежит языку'); readkey; end; end.
8.06. Контрольная распечатка.
Введите строку символов 221b2 Данная строка не принадлежит языку
219
Введите строку символов 221b221b221b Данная строка принадлежит языку Введите строку символов b21
Данная строка принадлежит языку Введите строку символов b21b21 Данная строка принадлежит языку Введите строку символов 22222222 Данная строка принадлежит языку
Ведите строку символов 221b221bb21b21b212222
Данная строка принадлежит языку Введите строку символов 211b Данная строка не принадлежит языку Введите строку символов Данная строка принадлежит языку
220