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

UptoLike

ВУЗ: 

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

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

Рубрика: 

202
),( qqx → ;
121
),( qqx → ,
21
),( qq →
ε
.
111
),( qqx → ,
222
),( qqx →
Для слова d=
1
x
1
x
1
x
1
x
2
x
2
x последовательность вычислений КА имеет вид:
1
x
1
x
1
x
1
x
2
x
2
x
0
q
1
x
1
x
1
x
1
x
2
x
2
q
2
x
1
x
1
x
1
x
1
x
2
q
2
x
2
x
1
x
1
x
1
x
2
q
1
x
2
x
2
x
1
x
1
x
2
q
1
x
1
x
2
x
2
x
1
x
1
q
1
x
1
x
1
x
2
x
2
x
1
q
ε
1
x
1
x
1
x
1
x
2
x
2
x
0
q
ε
1
x
1
x
1
x
1
x
2
x
2
x
В дальнейшем, если не оговорено противное, будем рассматривать левосторонние
КА.
Легко понять, что множество команд КА представляет собой функцию,
называемую функцией перехода автомата, которую обозначим через Υ. Она определена
на множестве (точнее подмножестве) декартового произведения Q
×
Y
V и принимает
значения в Q. В общем виде её можно записать
),(
ijk
xqYq
=
. Функция переходов может
быть задана матрицей переходов, представляющей собой прямоугольную матрицу, строки
которой помечены символами Qq
j
ε
, а на пересечении
i
q строки и
j
q столбца ставится
значение функции
k
q . Функцию Y можно доопределить на множестве Q×
*
Y
V следующим
образом. Пусть
*
T
Vd ∈ , причем
i
xdd
1
= . Тогда )),(()(
1 ijj
xdqYYdqY
=
.
Таким образом, формально любой конечный автомат A можно записать в виде
пятерки множеств:
{}
'),,(,,,
0
QxqYqQVA
k
=
, где
k
V - входной алфавит, Q- алфавит
состояний, Qq ∈
0
-начальное состояние, Y(q,x)- функция переходов, a Q’ Q≡ -
множество заключительных состояний автомата.
КА можно также задать в виде ориентированного нагруженного графа. Каждому
состоянию Qq
j
∈ соответствует вершина графа, а каждой команде
kij
qxq →),(
сопоставляется дуга, ведущая из вершины
j
q в вершину
k
q и помеченную символом
i
x .
Пример 3.9. На рис. 3.8 (а,б) приведены соответственно таблицы переходов
автомата А и В, а на рис.3.9 (а,б) – их графы
а) б)
рис.3.8
Q
T
V
0
q
1
q
2
q
1
x
-
1
q
1
q
2
x
2
q
-
2
q
B
-
0
q
-
Q
T
V
0
q
1
q
2
q
1
x
2
q
-
2
q
2
x
-
1
q
1
q
B
-
0
q
-

Страницы