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

	Конфигурация

Очевидно, для того чтобы эта строка была распознана, нам необходимо на вершине стека получить знак , что невозможно ипользуя команды МА .

Задача 34

Задан МА :

a)  алфавит входных знаков ;

b)  множество состояний ;

c)  стековый алфавит ;

d)  начальная конфигурация ;

e)  магазинное отображение

.

Построить грамматику, порождающую язык, принимаемый автоматом .

Решение

1.  Для решения этой задачи воспользуемся теоремой о МА и КС-языке.

a)  Грамматика .

b)  Алфавит терминальных знаков .

c)  Обозначим заключительное состояние как .

d)  Аксиома , где .

e)  Алфавит нетерминальных знаков , тогда .

f)  Если в имеется команда , где , , , то в добавляем всевозможные продукции вида , где . Для команд вида в добавляем продукцию . Аксиому строим таким образом, что при извлечении из стека любого префикса начальной конфигурации автомат переходит из начального в заключительное состояние, что эквивалентно принятию такого множества строк, которые будут соответствовать построенной аксиоме. Тогда получим

2.  Приведём полученную грамматику.

a)  Удаляем из множества продукций грамматики все продукции, содержащие заключительное состояние не в конце строки в левой части. Получаем

b)  Строим множество достижимых знаков .

c)  Строим множество производящих знаков .

d)  В итоге получаем:

-  ;

-  ;

-  .

Занятие 2.4. Конечный автомат (КА)

Задача 35

Пусть язык содержит строки в алфавите такие, что справа от знака всегда находится знак . Синтезировать КА, распознающий строки языка .

Решение

1.  Построим регулярную грамматику

a)  Множество продукций .

b)  Алфавит терминальных знаков .

c)  Алфавит нетерминальных знаков .

2.  В соответствии с теоремой о представимости регулярных языков конечными автоматами строим КА , распознающий строки языка .

a)  Входной алфавит.

b)  Выходной алфавит .

c)  Множество состояний , где - заключительное состояние.

d)  Начальное состояние .

e)  Систему команд строим следующим образом: для каждой продукции , где , в добавляем команду , а для каждой команды в добавляем команду . Тогда получим .

Задача 36

КА задан в виде графа.

Получить формальную грамматику для языка порождаемого этим КА и для языка распознаваемого этим КА.

Решение

1.  Строим грамматику для языка, распознаваемого этим КА.

a)  Алфавит терминальных знаков .

b)  Алфавит нетерминальных знаков .

c)  Аксиома .

d)  Множество продукций строим следующим образом: в добавляем продукцию и для каждой команды , где , , в добавляем продукцию . Тогда получим .

2.  Строим грамматику для языка, порождаемого этим КА.

e)  Алфавит терминальных знаков .

f)  Алфавит нетерминальных знаков .

g)  Аксиома .

h)  Множество продукций строим следующим образом: в добавляем продукцию и для каждой команды , где , , в добавляем продукцию . Тогда получим .

Задача 37

Построить КА, вычисляющий для пары строк над алфавитом их двоичную сумму. Входные данные начинаются с битов с наименьшим весом.

Задача 38

Построить КА, осуществляющий сложение двоичных чисел в дополнительном коде (см. задачу 36).

Замечание: .