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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

95
В качестве примера рассмотрим конечный автомат (назовём его ав-
томат A), который обрабатывает случайную последовательность гербов и
цифр, получающуюся в результате многократного подбрасывания моне-
ты, и производит отметки при появлении каждого первого герба в серии
гербов и каждой, исключая первые две, цифры в серии цифр.
Входным алфавитом автомата A является множество X = {цифра
(Ц), герб (Г)}, выходным алфавитом − множество Z = {отметка (
∨
), нет
отметки (−)}, а множеством состояний − множество S = {нет появления
ни цифры ни герба (НПН), появление первой цифры (ППЦ), появление
двух цифр (ПДЦ), появление первого герба (ППГ)}. Отметка производится
в случаях, когда автомат находится в состоянии ПДЦ и входом является Ц,
или когда автомат находится в состоянии, отличном от состояния ППГ и
входом является Г. При любом настоящем состоянии и появлении на
входе символа Г автомат переходит в состояние ППГ. Если на вход авто-
мата поступает цифра, то он из состояний НПН и ППГ переходит в со-
стояние ППЦ, а из состояний ППЦ и ПДЦ переходит в состояние ПДЦ.
Ещё одним примером конечного автомата является автомат A1 для
подсчёта числа слов, начинающихся с un и заканчивающихся на d (united,
understand и т.п.), в тексте, который составлен из 26 строчных букв анг-
лийского алфавита и пробелов. Пробел обозначим символом π, а все бук-
вы, кроме d, n и u, − символом λ.
Входным алфавитом автомата A1 является множество X = {d, n, u,
π, λ}, выходным алфавитом − множество Z = {считать, не считать},
множеством состояний − S = {новое слово, ожидание нового слова, появ-
ление u, появление u-n, появление u-n-d}.
При настоящем состоянии автомата A1 появление u-n-d и входе π на
его выходе появляется символ считать, а во всех остальных случаях −
символ не считать. Если автомат находится в любом состоянии и на
вход подаётся символ π, автомат переходит в состояние новое слово. При
состоянии новое слово и входе u наступает состояние появление u, а при
входе d, n или λ − состояние ожидание нового слова. При настоящем со-
стоянии появление u и входе n автомат переходит в состояние появле-
ние u-n, а при входе d, u или λ − в состояние ожидание нового слова. Если
состоянием в данный тактовый момент является появление u-n или появ-
ление u-n-d и на вход поступает d, то наступает состояние появление
u-n-d, а при входе n, u или λ − состояние появление u-n. При состоянии
ожидание нового слова и входе, отличном от π, автомат переходит в то
же самое состояние.
Последовательность входных символов вида
1
i
ξ
,
2
i
ξ
, ...,
l
i
ξ
назы-
вается входной последовательностью. Входная последовательность
1
i
ξ
,
2
i
ξ
, ...,
l
i
ξ
имеет длину l и вызывает выходную последовательность

Страницы