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

UptoLike

ВУЗ: 

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

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

Рубрика: 

39
далее движение к следующей вершине графа S
4
, и встречающуюся при этом
букву m
2
приписываем справа к первой букве слова (итак, имеем m
1
m
2
).
Отметим при этом, что учет петли, стоящей около S
2
, приведет к образованию
другого слова, которое мы составим после завершения построения первого.
Находясь в вершине S
4
, замечаем, что из нее выходит только одна дуга S
4
S
0
,
входящая в S
0
. Около нее стоит буква m
1
, котор пишем справа от
имеющихся уже первых букв m
1
m
2
(получаем m
1
m
2
m
1
). В итоге, на графе
пришли к начальному состоянию S
0
, что означает, что просс формирования
слова
m
1
m
2
m
1
завершен.
Вернемся теперь к случаю петли, стоящей около вершины S
2
. В момент
прихода в S
2
имеем только первую букву слова m
1
. Наличие ориентированной
петли около S
2
означает, что, оставаясь а вершине S
2
, к записи, которая
существовала к данному моменту (m
1
), следует добавить справа букву,
стоящую у петли, т.е. m
3
, что дает m
1
m
3
. Дале повторяя путь, пройденный от
S
2
к S
0
(через S
4
), дополним эту запись буквами m
2
,m
1
.
В итоге получаем другое слово языка m
1
m
3
m
2
m
1
.
Рассмотрение пункта а) на этом не заканчивается. В начале этого пункта,
мы отметили, что, выходя из S
1
, из двух возможных вершин S
2
, S
4
мы выбрали
S
2
, оставив не рассмотренной вершину S
4
. Вернемся теперь к этому случаю.
Двигаясь от S
1
к S
4
, записываем первую букву нового слова m
2
, а перемещение
из S
4
в S
0
завершает слово буквой m
1
. Итак, получаем следующее по счету
слово языка
m
1
m
2
. На этом завешается рассмотрение пункта а).
Переходим к написанной в пункте б) вершине S
3
. Повторяя рассуждения,
аналогичные тем, которые были проведены выше, приходим к выводу, что
рассмотрение оставшейся возможности дает только одно слово m
3
m
1
.
Окончательно получаем, что исследуемый язык Я состоит из четырех
слов.
Я={ m
1
m
2
m
1
, m
1
m
3
m
2
m
1
, m
2
m
1
, m
3
m
1
}.
§3.3 Понятия и типы дискретных автоматов.
Под дискретным автоматом (ДА) понимаюустройство,
осуществляющее переработку и преобразование дискретной информации, т.е.
информации, поступающей в это устройство в отдельно взятые моменты
времени.
На практике наиболее распространенным является случай, когда
дискретная информация поступает в автоматическое устройство в виде
двоичного сигнала, т.е. сигнала, который принимает всего лишь два значения 0
и 1. Такой сигнал и соответствующее ему устройство будем называть
двоичным.
Пусть ДА имеет K входов, на которые подаются двоичные сигналы x
1
, x
2
,
... , x
k
и q выходов, на которых появляются двоичные сигналы y
1
, y
2
, ... , y
q
.
Совокупность входных (x
1
, x
2
, . , x
k
) и выхоых (y
1
, y
2
,... , y
q
) сигналов
будем трактовать как векторы X и Y соответствующей размерности. Условимся
значения сигналов в текущий (данный) момент времени снабжать индексом n, а
в прошедший и будущий моменты - соответственно индексами n-1 и n+1.
Рассматривают два типа дискретных автоматов:

Страницы