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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
из одного состояния органов речи в другое появляется звук, которому в
алфавите разговорного языка соответствует определенная буква. Так же как и в
формальных языках, слова нашего языка разделены интервалами (аналог m
0
);
причем, на каждом интервале органы речи пребывают в нейтральном состоянии
(аналог S
0
).
§ 3.2 Изображение языка в виде графа.
Построение слов в языке очень удобно проводить с помощью графа
языка, являющееся его геометрической интерпретацией. В вершинах этого
графа помещаются элементы множества M
N
, т.е. состояния языка Я, которые
затем соединяют дугами в соответствии с правилами грамматики языка (23).
Рядом с дугой S
k
S
l
, выходящ из вершины графа S
k
и входящей в вершину
S
l
,, пишут появляющуюся при этом букву составляемого слова m
i
.
Проиллюстрируем процесс конструирования языка Я на конкретном примере.
Пример 11.
Язык Я с алфавитом M={m
1
, m
2
, m
3
} задан совокупностью
следующих правил грамматики
S
1
::=S
0
m
0
, S
3
::=S
0
m
0
, S
2
::=S
1
m
1
, S
2
::=S
2
m
3
,
S
4
::=S
1
m
2
|S
2
m
2
|
3
m
3
, S
0
::=S
4
m
1
. (24)
Изобразить в виде графа структуру языка Я и построить совокупность слов,
порождаемых грамматикой этого языка.
Решение. Заметим, прежде всего, что, если среди правил грамматики
языка встречается соотношение, в правой части которого фигурирует несколько
состояний S
i
(как в случае нашего примера), это означает, что переход к
состоянию, стоящему в левой части, происходит из каждого состояния,
написанного справа. Так, для пятого из соотношений (24) переход в состояние
S
4
происходит из каждого состояния S
1
, S
2
, S
3
с появлением соответственно
букв m
2
, m
2
, m
3
.
Построение графа начинаем с вершины S
0
, котораяоответствует
начальному состоянию языка (рис. 13). Среди соотношений (24) отбием
такие, в правой части которых есть S
0
. В нашей задаче это S
1
::=S
0
m
0
, S
3
::=S
0
.
Вершину графа S
0
соединяем дугами, выходящими из S
0
и входящими в
вершины S
1
и S
3
. Рядом дугами пишем m
0
- символ пробела между словами
языка. Вершины S
1
и S
3
должны быть соединены с

Страницы