Задачи:

2.1. Локомотив L и вагоны стоят на пути, показанном ниже, в порядке (слева направо), который может быть представлен строкой LABCD Пред­положим, что локомотив можно произвольно отцеплять и сцеплять с отдель­ными вагонами, стрелки могут занимать произвольное положение и локомотив может тянуть и толкать тот вагон, к которому он прицеплен Укажите мно­жество правил переписывания для строк, которое можно было бы использовать с целью создания представлений для всех возможных расположений ваго­нов и локомотива на прямом отрезке пути

2.2. Дуга между вершиной n_i и вершиной n_j, следующей за ней, назы­вается невозвратной, если n_i недостижима из n_j. Дайте два примера задач, для которых графы в пространстве состояний содержат невозвратные дуги.

2.3. Покажите, найдя соответствующий путь на графе, представляющем пространство состояний, что строка (((), ()), (), ((), ())) является предло­жением S в грамматике, определяемой следующими правилами переписыва­ния

a) S← ()

b) A← S

c) А←А,А

d) S← (А)

В этих правилах переписывания считается, что символ, стоящий слева от стрелки, может быть подставлен вместо подстроки символов, стоящей справа от стрелки, в любом месте строки, в котором эта подстрока встретилась

2.4. Найдите форму описания состояний, операторы и критерии достиже­ния цели для следующей задачи о кувшинах

Даны кувшин с водой емкостью 5 галлонов и пустой кувшин емкостью 2 галлона. Как получить ровно один галлон в кувшине емкостью в 2 галлона? Воду можно либо выливать, либо переливать из одного кувшина в другой

Начертите часть дерева перебора, соответствующего тем шагам, которые вы предпринимаете в поиске решения

2.5. Для следующей задачи о восьми ферзях укажите форму описания состояний, операторы и критерий достижения цели.

Разместить 8 ферзей на обычной шахматной доске так, чтобы на каждой горизонтали, вертикали и диагонали стояло не более одного ферзя.

Начертите часть графа состояний и снабдите его вершины и дуги соответ­ствующими описаниями

2.6. Напишите программу для вычислительной машины, порождающую-множество строк, которые могут быть получены заменой подстроки S₁ под­строкой S₂ во всех местах данной строки S, где стоит подстрока S₁.

18