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

UptoLike

ВУЗ: 

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

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

Рубрика: 

30
Множество V
1
содержит два специальных символа Z
l
и Z
p
, называемых гра-
ничными маркерами, которые не позволяют головке управляющего устройства уйти с
той части ленты, на которой задана входная цепочка.
Таким образом, линейно-ограниченный автомат является недетерминирован-
ной машиной Тьюринга с ограничением на длину цепочки рассматриваемых симво-
лов. Ситуация линейно-ограниченного автомата и элементарное действие определя-
ются так же, как и для машины Тьюринга. Язык, допускаемый линейно-
ограниченным автоматом, определяется как множество:
L(М) = {α | α∈ (V
1
– { Z
,l
Z
p
})* ∧ (q
0
, Z
l
α Z
p
, 1) |
*
(q
f
, β, i)},
где q
f
= F, β ∈ V
2
*, 1 ≤ i ≤ n (n – длина исходной цепочки).
В настоящее время неизвестно, является ли класс языков, допускаемых детер-
минированными линейно-ограниченными автоматами, собственным подклассом
класса языков, допускаемых недетерминированными линейно-ограниченными авто-
матами. Однако, для недетерминированных линейно-ограниченных автоматов уста-
новлено, что допускаемые ими языки являются НС-языками. Более того, доказано,
что для любого НС-языка можно построить недетерминированный линейно-
ограниченный автомат.
2.4. Автоматы с магазинной памятью и бесконтекстные языки
Автоматы и преобразователи с магазинной памятью играют важную роль при
построении автоматно-лингвистических моделей различного назначения, связанных с
использованием бесконтекстных (контекстно-свободных) языков. В частности, такие
устройства используются в большинстве работающих программ для синтаксического
анализа программ, написанных на различных языках программирования, которые во
многих случаях можно рассматривать как бесконтекстные.
2.4.1. Автоматы с магазинной памятью
В отличие от конечных автоматов, рассмотренных ранее, автоматы и преобра-
зователи с магазинной памятью снабжены дополнительной магазинной памятью (ра-
бочей лентой) (рис. 2.5).
Входная лента
Управляющее
устройство
Выходная лента
Магазинная память
а
в
сq
Рис. 2.5. Автоматы с магазинной памятью

Страницы