Синтез цифровых автоматов. Захаров Н.Г - 30 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

29
(q, A
1
... A
n
, 0) | (q′, X A
1
... A
n
, 0);
(q, A
1
... A
n
, n+1) | (q′, A
1
... A
n
X, n).
Вторая из этих команд меняет их так:
(q, A
1
... A
n
, 0) | (q′, X A
1
... A
n
, 2);
(q, A
1
... A
n
, n+1) | (q′, A
1
... A
n
X, n+2).
Если ситуации (q
1
, β
1
, i
1
) и (q
2
, β
2
, i
2
) связаны между собой некоторым числом
элементарных действий, то между ними имеет место отношение:
(q
1
, β
1
, i
1
) |
*
(q
2
, β
2
, i
2
).
Язык, допускаемый машиной Тьюринга Т, это:
L(Т) = {α | α∈ V
1
* ∧ (q
0
, α, 1) |
*
(q
f
, β, i)},
где q
f
= F, β ∈ V
2
*, i ≥ 0.
Другими словами, если, преобразуя входную цепочку α, машина Т окажется в
одном из своих заключительных состояний, эта цепочка допускается данной машиной.
Так же как для автоматов введем понятие недетерминированной машины Тью-
ринга. Ее отличие от детерминированной заключается в том, что функция δ отобра-
жает множество Q x V
2
в множество подмножеств Q x (V
2
– {B}) x {Л, П}.
Если язык L порождается грамматикой типа 0, то L допускается некоторой ма-
шиной Тьюринга. Верно и обратное, если язык L допускается некоторой машиной
Тьюринга, то L порождается грамматикой типа 0.
2.3. Машины Тьюринга и линейно-ограниченные автоматы
Рассмотренные типы автоматов и машин Тьюринга часто используются для по-
строения автоматно-лингвистических моделей, предназначенных для распознавания
языков. Необходимо знать, разрешима ли для них так называемая проблема распо-
знавания или нет.
Эта проблема заключается в следующем. Пусть есть некоторая цепочка α на
входе машины Тьюринга, которая допускает язык L. Всегда ли можно установить
принадлежность цепочки α к языку L за конечное число элементарных действий этой
машины?
Однако не для всех языков типа 0 эта проблема разрешима. Другими словами,
можно подобрать такой язык типа 0, что соответствующая ему машина Тьюринга для
некоторой цепочки α за конечное число элементарных действий не сможет устано-
вить принадлежность ее к данному языку. Поэтому машина Тьюринга в общем виде
не нашла применения в реальных кибернетических моделях; языки типа 0 также не
используются. Наибольший интерес представляют различные специальные классы
машин Тьюринга, к которым можно отнести автоматы, рассмотренные выше, а также
так называемые линейно-ограниченные автоматы, допускающие языки типа 1 (НС-языки).
Линейно-ограниченным автоматом называется шестерка:
М = (V
1
, V
2
, Q, δ, q
0
, F),
где V
1
= {a
1
, ..., a
m,
Z
,l
Z
p
} – конечный входной алфавит;
V
2
= {А
1
, ..., А
k
} – конечное множество ленточных символов, причем V
1
≤ V
2
;
Q = {q
0
, q
1
, ..., q
n-1
} – конечное множество состояний;
q
0
∈ Q – начальное состояние;
F ⊆ Q – множество заключительных состояний;
δ – функция, отображающая Q x V
2
в множество подмножеств Q x V
2
x {Л, П}.

Страницы