Дискретная математика. Громов Ю.Ю - 67 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

67
Пусть G – некоторая совокупность правил, с помощью которых в M
порождаются все слова, принадлежащие языку Я, и только они. Совокуп-
ность правил G будем называть грамматикой языка Я. Два языка назы-
ваются эквивалентными, если множества слов, из которых они состоят,
совпадают. Две грамматики G
1
и G
2
языка Я будем называть эквивалент-
ными, если они порождают эквивалентные языки.
Условимся говорить, что грамматика G является грамматикой с ко-
нечным числом состояний, если правила порождения слов в алфавите
M = {m
1
, m
2
, ..., m
n
} задаются следующим образом.
Существует конечное множество состояний {s
0
, s
1
, ..., s
r
} и каждому
состоянию s
j
( j = 1, 2, ..., r) сопоставляется набор пар вида (m
i
, s
q
), где
i ∈ {1, 2, ..., n}, q ∈ {1, 2, ..., r}. Состоянию s
0
сопоставляются пары вида
(m
0
, s
h
), где h ∈ {1, 2, ..., r}. Символ m
0
это специальный знак пробела
между словами.
Конструирование слов происходит так. Из состояния s
0
совершают
переход в любое состояние s
q
из тех состояний, которые являются вто-
рыми членами упорядоченных пар вида (m
0
, s
q
), и в начале слова ставят
знак пробела. Исходя из пар, сопоставленных выбранному состоянию s
q
,
берут любую пару (m
i
, s
l
). Этот выбор определяет следующее состояние s
l
и первый символ m
i
конструируемого слова. Далее процесс построения
слова происходит аналогичным образом. Заканчивается слово при пере-
ходе к заключительному состоянию, как правило, состоянию s
0
.
Язык, порождаемый грамматикой с конечным числом состояний, на-
зывается языком с конечным числом состояний. Структуру таких языков
удобно изображать в виде графа, вершины которого сопоставлены
состояниям s
j
(j = 1, 2, ..., r), а дуги – парам (m
i
, s
q
), где i ∈ {1, 2, ..., n},
q ∈ {1, 2, ..., r}. На рисунке 30 приведён пример такого графа.
С помощью грамматики, задаваемой этим графом, порождается
язык, который состоит из следующего множества слов: {m
1
m
1
, m
1
m
2
m
3
m
1
,
m
1
m
2
m
3
m
3
m
1
}.
s
0
s
1
s
2
s
3
s
4
s
5
m
0
m
1
m
1
m
1
m
2
m
3
m
3
m
3
Рис. 30

Страницы