Теория алгоритмов и формальных языков. Мелихов А.Н - 66 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

а) б)
рис.3.9
Итак, мы рассмотрели конечные автоматы, допускающие языки. Если снабдить КА
выходной лентой, ограниченной слева и неограниченной справа и передвигающейся
справа налево, на которой записываются буквы из некоторого выходного алфавита
автомата, то мы получим односторонний конечный преобразователь или конечный
автомат с выходами. Такие автоматы реализуют в общем случае
частичное отображение
множества всех слов входного алфавита и множество всех слов выходного алфавита.
Рассмотрим способы задания и функционирования таких автоматов. Пусть
{}
mk
xxxV ,,,
21
K= - алфавит входных символов автомата, а
*
k
V
- множество всех слов в
k
V .
Любое подмножество множества называют событием в этом алфавите. Пусть
{}
nY
yyyV ,,,
21
K= - алфавит выходных символов автомата. Примем, как и ранее, что
алфавит состояний автомата
{
}
k
qqqQ ,,,
10
K= . Конечный автомат с выходами работает
аналогично конечному автомату без выходов с той разницей, что в каждом такте работы в
ячейку выходной ленты записывается некоторая буквы выходного алфавита, после чего
выходная лента, также как и входная, сдвигается на одну ячейку влево. Формально
функционирование конечного автомата с выходами можно описать командами вида
()
(
)
jkil
yqxq ,, → и задать двумя функциями Y и Ψ, называемыми соответственно
функцией переходов и функцией выходов, которые имеют вид
()
=
=
jilk
yxqYq ,, Ψ ),(
il
xq .
Каждую из них можно задавать в виде таблиц. Таблица переходов строится так же, как и
для КА без выходов, строки которой помечены входными буквами, а столбцы-
состояниями, содержит на пересечении
i
x строки и
l
q столбца выходную букву
i
y . Кроме
таблиц переходов и выходов конечный автомат с выходами можно задать в виде
ориентированного нагруженного графа, дуги которого помечаются кроме входных и
выходными буквами.
Пример 3.10. пусть задан конечный автомат с выходами
{
}
),(),,(,,,,
0
xqxqYqQVVA
yx
ψ
= , где
{
}
{
}
{
}
21021321
,,,,,,, qqqQyyVxxxV
yx
=
=
=
, а функции
),( xqY и ),( xq
ψ
заданы таблицами, показанными соответственно на рис.3.10 (а,б):
a)
б)
рис.3.10
Q
x
V
0
q
1
q
2
q
1
x
1
q
2
q
1
q
2
x
0
q
1
q
-
3
x
2
q
-
0
q
Q
x
V
0
q
1
q
2
q
1
x
2
y
1
y
2
q
2
x
1
y
2
y
-
3
x
1
y
-
1
y
2
q
1
x
0
q
1
x
0
q
2
x
2
x
2
x
1
q
B
1
x
1
x
1
x
2
x
1
x
1
x
1
q
B
1
x
2
x
2
x
2
q

Страницы