Основы дискретной математики. Щипцов В.В - 38 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

38
другими вершинами графа в
соответствии с правилами (24).
1) Начнем, например, с
вершины S
1
. Среди соотно-
шений (24) отбираем такие, в
правой части которых есть S
1
.
рис. 13
В нашем случае это: S
2
::=S
1
m
1
,
S
4
::=S
1
m
2
|S
2
m
2
| S
3
m
3
. В соответствии с этими
соотношениями вершину S
1
соединим дугами с вершинами S
2
, S
4
и рядом с
ними напишем m
1
, m
2
. Далее рассмотрим соотношения, в правой части которых
есть либо S
2
, либо S
4
(S
0
::=S
4
m
1
, S
2
::=S
3
, S
4
::=S
1
m
2
|S
2
m
2
|S
3
m
3
) При эт
начинаем с тех из них, в левой части которых нет S
0
. В нашей задаче это будет
второе и третье соотношения, написанные в скобках. В соответствии с первым
их них S
2
::=S
2
m
3
око вершины S
2
рисуем дугу, выходящую и входящую в S
2
,
и около нее ставим m
3
. Другое соотношение S
4
::=S
1
m
2
|S
2
m
2
|S
3
m
3
означает, что
вершину S
2
нужно соединить дугой, входящей в S
4
, поставив рядом с ней m
2
.
Переходим далее к соотношению S
0
::=S
4
m
1
, которое означает, что вершину S
4
следует соединить дугой с вершиной S
0
, и напишем рядом с дугой m
1
. В итоге
пришли к начальному состоянию S
0
, что подтверждает правильность наших
построений.
2) Осталась еще не рассмотренной вершина S
3
. Среди правил грамматики
данного языка (24) есть только одно, правая часть которого содержит S
3
, это
S
4
::=S
1
m
2
|
m
2
|S
3
m
3
. В соответствии с ним вершину S
3
соединяем с вершиной
S
4
и около дуги пишем m
3
. Попада в вершину S
4
, которая уже была
рассмотрена в пункте 1. На этом построение графа закончено.
Обсудим далее процедуру конструирования слов данного языка. Из
начального состояния S
0
(рис. 13) совершим переход в любую из вершин графа
S
i
по дуге S
0
S
i
, ведущей в S
i
. В нашем случае это можно сделать двояким
образом: из вершины S
0
можно попасть
а) либо в вершину S
1
,
б) либо в вершину S
3
.
Исследм каждую из возможностей. Возьмем, например, вершину S
1
.
Появлщийся при переходе из S
0
в S
1
символ m
0
, являюйся знаком
пробела между словами, при этом не пишется. В свою очередь из вершины S
1
можно попасть либо в вершину S
2
, либо в вершину S
4
.
Выберем, например, вначале вершину S
2
, при этом буква m
1
, стоящая с
дугой S
1
S
2
, будет первой буквой конструируемого слова. Из S
2
продолжаем

Страницы