Сборник задач по теории автоматов (стр. 6 )

Решение для пункта b

1.  Грамматика является КС-грамматикой, так как все её продукции имеют вид .

2.  Найдём множество существенных нетерминальных знаков.

A.  Найдём множество достижимых знаков. Так как в первой продукции множества содержатся все нетерминальные знаки множества , то есть множество достижимых знаков.

B.  Найдём множество производящих знаков .

a)  Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.

b)  Строим следующее приближение множества производящих знаков , где - множество тех нетерминальных знаков, которые непосредственно порождают строки состоящие из терминальных знаков и знаков множества . Тогда получаем .

c)  Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т. е. все знаки множества .

d)  Так как , то .

C.  Таким образом, получили, что все нетерминальные знаки грамматики существенны.

3.  Строим такой вывод в грамматике из существенного нетерминального знака , что и , где и состоят из существенных и терминальных знаков:

-  ;

-  ;

-  .

4.  Так как не смогли получить вывод в грамматике , описанный в пункте 3, то язык конечен.

Задача 21

Грамматика задана множеством продукций

Найти все строки языка такие, что .

Задача 22

КС-грамматика задана множеством продукций

Найти все строки языка , содержащие 3 знака .

Раздел 2. Основы общей теории автоматов

Занятие 2.1. Машина Тьюринга (МТ)

Задача 23

МТ задана таблицей.

\

Найти её заключительную конфигурацию.

Решение

Применяем к начальной конфигурации команды МТ до тех пор, пока МТ не перейдёт в заключительное состояние:

Задача 24

Построить МТ в алфавите переводящую конфигурацию в конфигурацию (которая умножает число представленное в унитарном коде на 2).

Решение

1.  Приводим примеры работы МТ:

-  при ;

-  при .

2.  Даём словесное описание алгоритма.

Проверяем, является ли текущим знаком знак . Если нет, то останавливаемся, иначе заменяем текущий знак на маркер , перемещаемся влево до первого знака и заменяем его на знак , перемещаемся вправо до маркера и заменяем его на знак , смещаемся вправо и повторяем сначала.

3.  Задаём МТ реализующую действия из пункта 2 в виде таблицы.

\

4.  Проверка: