Машина Тьюринга. Линейно-ограниченные автоматы.
Машина
Тьюринга называется линейно-ограниченным
автоматом, если существует такое число
С, что в процессе обработки входной
ленты, на которой в начальной конфигурации
находится цепочка
,
машина не может использовать более, чем
С
ячеек ленты. Таким образом, объем памяти
такого автомата не является неограниченным,
как у машины Тьюринга, а определяется
длиной последовательности входных
символов. (Линейно
ограниченный автомат (lba)
есть недетерминированная одноленточная
машина Тьюринга, которая никогда не
покидает те ячейки, на которых размещен
ее ввод.
Формально он определяется следующим образом.
Определение. Линейно ограниченным автоматом называется формальная система
в
которой
Q — множество состояний;
q0 Q— начальное состояние;
F
Q
—
множество
конечных состояний;
Г— алфавит допустимых символов ленты;
—
алфавит
входных символов,
который содержит два особых символа:
¢ и $ — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером);
—
отображение
типа
Движения линейно ограниченного автомата описываются в терминах конфигураций. Конфигурация lba M обозначается как (q, A1A2…An, i), где q Q;
A1 , A2,…, An Г; i — целое, причем 1 <=i <=n . Согласно определению A1 = ¢,
An = $.
Если
( p,
A,
L)
(q,
Ai)
и
i >
1, то
(q,
A1A2…An,
i)
( p,
A1A2…Ai
–
1
AAi+1…An,
i –
1).
Если ( p, A, R) q, Ai) и i < n, то (q, A1A2…An, i) ( p, A1A2…Ai – 1 AAi+1…An, i + 1).
Другими словами, lba M печатает символ A на месте Ai, изменяет свое состояние на p и продвигает свою головку влево или вправо, не выходя из области, в которой символы находились изначально
Системы Линденмайера (l-системы). Внутреннее устройство l-систем.
Формальные грамматики используются не только в синтаксическом анализе. Системы Линденмайера являются примером применения формальных грамматик в задаче, не имеющей никакого отношения к синтаксическому анализу.
L-системы названы так в честь своего изобретателя, шведского ботаника Аристида Линденмайера, сумевшего показать, что структура растений может быть очень точно смоделирована при помощи формальных грамматик.
Идея состоит в том что сгенерированная грамматикой строка может быть визуализирована как в черепашьей графике.
L
-системы
предназначены для моделирования
растений. Поэтому представим, что
растение состоит из элементов трех
видов: участок ствола (1), левый лист (L)
и правый лист (R).
Тогда простейшую конфигурацию, состоящую
из короткого ствола, на котором растут
два листа, можно записать в виде строки
ILR.
Учитывая это, системы Линденмайера позволяют вития конфигурации в виде
предок -> потомок
Используя эту запись, можно «вырастить» куст любой высоты. Добавив к описанию куста новый элемент — «корень» (А) и указав способ его развития:
А -> AILR
Изначально наш куст будет состоять всего лишь из одного корня. После трехкратного применения правила роста можно получить куст, состоящий из трех сегментов:
А -> AILR -> AILRILR -> AILRILRILR
Функционирование L-систем подразделяется на два независимых аспекта:
механизм генерации строк на основе начальной строки (называемой аксиомой) и некоторой разновидности формальной грамматики,
полученная в итоге строка должна интерпретироваться подсистемой визуализации, чтобы на экране появился осмысленный рисунок.
В процессе генерации строки, в отличие от обычной грамматики, где на каждом шаге применялось лишь одно правило, в L-системах одновременно происходит замена всех символов, для которых существуют правила развития (хотя бы потому, что все части растения развиваются одновременно, а не по очереди).
Визуализация происходит по принципу черепашьей графики.
