Математическая логика и теория алгоритмов. Стенюшкина В.А. - 104 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

над магазином (ввести/вывести один символ или не менять содержимое
магазина);
над состоянием (перейти в новое или остаться в прежнем);
над входом (перейти к следующему входному символу или оставить те-
кущий до следующего шага)
Множество правил перехода называется управляющем устройством.
Магазинная память-автомат называется магазинной памятью-распознавателем,
если он имеет два выхода: «допустить», «отвергнуть».
Пример – Автомат А={0,1,├}, Q={q
1
,q
2
}, Г={z, #}, где ├ - символ конца
цепочки на входной ленте, # - маркер дна магазина, q
1
– начальное состояние
магазина, # - начальное содержимое магазина, имеет управляющую таблицу
6.3.
Таблица 6.3
Вход
Магазин
q
1
0 q
1
1
q
1

z q
1
ввести сдвиг
q
2
ввести сдвиг
отвергнуть
# q
1
ввести сдвиг
отвергнуть
отвергнуть
Вход Магазин
q
2
0 q
2
1
q2

z
отвергнуть
q
2
ввести сдвиг
отвергнуть
# отвергнуть отвергнуть допустить
Этот автомат распознает слова языка L={0
n
1
n
| n≥1}.
Работа магазинной памяти-автомата при распознавании конкретной це-
почки может быть представлена последовательностью конфигураций, опреде-
ляемых содержимым магазина, состоянием автомата, входом. В частности, при
анализе входного слова 000 111 эта последовательность представлена таблицей
6.4.
Таблица 6.4
Магазин Состояние Вход
# q
1
000 111├
# z q
1
00 111 ├
# zz q
1
0 111├
# zzz q
1
111├
# zz q
2
11├
# z q
2
1├
# q
2
├
Выход Допустить 
       над магазином (ввести/вывести один символ или не менять содержимое
магазина);
       над состоянием (перейти в новое или остаться в прежнем);
       над входом (перейти к следующему входному символу или оставить те-
кущий до следующего шага)
       Множество правил перехода называется управляющем устройством.
Магазинная память-автомат называется магазинной памятью-распознавателем,
если он имеет два выхода: «допустить», «отвергнуть».
       Пример – Автомат А={0,1,├}, Q={q1,q2}, Г={z, #}, где ├ - символ конца
цепочки на входной ленте, # - маркер дна магазина, q1 – начальное состояние
магазина, # - начальное содержимое магазина, имеет управляющую таблицу
6.3.
       Таблица 6.3

Магазин           Вход
                  q10                q11                q1
z                 q1                 q2
                  ввести сдвиг       ввести сдвиг       отвергнуть
#                 q1
                  ввести сдвиг       отвергнуть         отвергнуть
Магазин           Вход
                  q20                q21                q2
z                                    q2
                  отвергнуть         ввести сдвиг       отвергнуть

#                 отвергнуть         отвергнуть         допустить

      Этот автомат распознает слова языка L={0n1n | n≥1}.
      Работа магазинной памяти-автомата при распознавании конкретной це-
почки может быть представлена последовательностью конфигураций, опреде-
ляемых содержимым магазина, состоянием автомата, входом. В частности, при
анализе входного слова 000 111 эта последовательность представлена таблицей
6.4.
      Таблица 6.4

Магазин                  Состояние                       Вход
#                        q1                              000 111├
#z                       q1                              00 111 ├
# zz                     q1                              0 111├
# zzz                    q1                              111├
# zz                     q2                              11├
#z                       q2                              1├
#                        q2                              ├
Выход                    Допустить

Страницы