Дискретная математика. Кулаков Ю.В - 48 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Пусть 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}.
На рис. 26 приведен пример такого графа.
С помощью грамматики, задаваемой этим графом, порождается язык, кото-
рый состоит из следующего множества слов: {m
1
m
1
, m
1
m
2
m
3
m
1
, m
1
m
2
m
3
m
3
m
1
}.
Порождение цепочек символов можно рассматривать как результат работы
некоторого гипотетического устройства, изображенного на рис. 27.
Вдоль бесконечной (в обе или одну сторону) ленты, разделенной на клетки,
перемещается управляющая головка (УГ). Заданы внешний алфавит M = {m
1
, m
2
, ..., m
n
}, символы кото-
рого называются буквами, внутренний алфавит S = {s
0
, s
1
, ..., s
r
}, символы которого называются со-
стояниями, и алфавит перемещений D = {П, Л, Н}. Все клетки ленты заполнены символами из M, по
одному символу в каждой клетке. Символ m
0
играет роль пустого символа (если в некоторой клетке
стоит m
0
, то «в клетке ничего не записано»). Предполагается, что вся бесконечная лента везде заполнена
символами m
0
, за исключением тех клеток, где записаны какие-либо другие символы из M.
Управляющая головка может находиться в тех или иных состояниях, харак-
теризуемых символами из S. Состояние s
0
особое. Если УГ находится в состоянии s
0
, то «машина не
производит никакой работы (выключена)». Предполагается, что в конце работы машина всегда перехо-
дит в s
0
. В процессе работы машины УГ может перемещаться в дискретные такты времени вдоль ленты.
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
Рис.
m
1
m
1
m
1
m
1
m
2
m
0
m
0
m
1
m
0
m
0
m
2
УГ
Рис. 27

Страницы