Языки и трансляции. Мартыненко Б.К. - 119 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

118
Глава 8
ЛИНЕЙНО ОГРАНИЧЕННЫЕ АВТОМАТЫ
И КОНТЕКСТНО-ЗАВИСИМЫЕ ЯЗЫКИ
§ 8.1. Линейно ограниченные автоматы
Линейно ограниченный автомат (lba linear-bounded automaton) есть
недетерминированная одноленточная машина Тьюринга, которая никогда не
покидаёт те ячейки, на которых размещён её ввод. Формально он определяется
следующим образом.
Определение 8.1. Линейно ограниченным автоматом называется
формальная система M =(Q, Σ, Γ, δ, q
0
, F), в которой Q — множество
состояний, q
0
∈
Q — начальное состояние, F ⊆ Q — множество конечных
состояний, Γ — алфавит допустимых символов ленты, Σ ⊆ Γ — алфавит
входных символов, который содержит два особых символа ¢ и
$ — левый и
правый маркеры, находящиеся с самого начала на концах входной цепочки для
того, чтобы предотвращать выход головки ленты за пределы участка, на
котором размещается входная цепочка (считается, что маркеры могут
использоваться только в этой роли: на место маркера нельзя записать какой-
нибудь другой символ ленты, и никакой символ ленты не может быть заменён
каким-нибудь маркером), δ — отображение типа Q ×Γ→2
Q ×Γ×{L, R}
.
Движения линейно ограниченного автомата описываются в терминах
конфигураций. Конфигурация lba M обозначается как (q, A
1
A
2
…A
n
, i), где q ∈
Q; A
1
, A
2
,…,A
n
∈ Γ; i — целое, причем 1≤ i ≤ n . Согласно определению
A
1
=¢, A
n
=$.
Если ( p, A, L) ∈ δ(q, A
i
) и i >1, то
(q, A
1
A
2
… A
n
, i) (p, A
1
A
2
… A
i –1
AA
i + 1
… A
n
, i – 1).
Если ( p, A, R) ∈ δ(q, A
i
) и i < n, то
(q, A
1
A
2
… A
n
, i) (p, A
1
A
2
… A
i – 1
AA
i + 1
… A
n
, i + 1).
Другими словами, lba M печатает символ A на месте Ai, изменяет свое
состояние на p и продвигает свою головку влево или вправо, не выходя из
области, в которой символы находились изначально.
Отношения на множестве конфигураций
,
,
или определяются
обычным для недетерминированных машин Тьюринга образом.
Определение 8.2. Языком, принимаемым линейно ограниченным автома-
том M, называется множество
{w | w ∈ (Σ \ {¢, $})
*
, (q
0
, ¢w$, 1) (q, ¢α$, i), q ∈ F, α∈Γ
*
, 1≤i≤n, n = |w| + 2}.
Определение 8.3. Линейно ограниченный автомат M является детермини-
рованным, если #δ(q, A) ≤ 1 для любых q∈ Q, A∈ Γ.
Неизвестно, является ли класс множеств, распознаваемых детерминирован-
ными линейно ограниченными автоматами, строгим подклассом множеств,
распознаваемых недетерминированными lba, или они совпадают. Конечно,
справедливо, что любое множество, принимаемое недетерминированным
M
−
−
M
−
−
M
−
−
n
M
−−
M
+
−−
*
M
−−
*
M
−−

Страницы