Решение. Начинаем построение списка

Начинаем построение списка .

Выполняем шаг 1 алгоритма. Для правила в список добавим ситуацию вида . Также для правила в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 2 алгоритма невозможно.

Выполняем шаг 3 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . Для ситуации в список также будут добавлены те же самые ситуации и . После этого шага списки ситуаций будут выглядеть следующим образом:

И снова для текущего содержимого списков выполнение шага 2 алгоритма невозможно.

Выполняем шаг 3 алгоритма. Ситуации вида и рассматривать не станем, так как они уже были рассмотрены при предыдущем выполнении шага 3 алгоритма. Рассмотрим ситуации и . Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Снова выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . Для ситуации в список также будут добавлены те же самые ситуации и . После этого шага списки ситуаций будут выглядеть следующим образом:

Снова выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для то же ситуации и правила вида в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Выполняем шаг 5 алгоритма. Для ситуации осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Всего таких ситуаций две: и . Для каждой такой ситуации в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Таких ситуаций две: и . Для них в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуация одна: . Для нее в список включаем следующую ситуацию: . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . Для ситуации в список также будут добавлены те же самые ситуации и . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . Для ситуации в список также будут добавлены те же самые ситуации и . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Выполняем шаг 5 алгоритма. Для ситуации осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Всего таких ситуаций две: и . Для каждой такой ситуации в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Таких ситуаций две: и . Для них в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуация одна: . Для нее в список включаем следующую ситуацию: . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленную в список ситуацию. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуация одна: . Для нее в список включаем следующую ситуацию: . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Выполняем шаг 5 алгоритма. Для ситуации осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Всего таких ситуаций две: и . Для каждой такой ситуации в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Таких ситуаций две: и . Для них список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.

Выполняем шаг 6 алгоритма. Для ситуации и правила вида в список добавим ситуацию вида . Для этой же ситуации и правила вида в список добавим ситуацию вида . Для ситуации в список также будут добавлены те же самые ситуации и . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя.

Начинаем построение списка .

Выполняем шаг 4 алгоритма. Для ситуации и учитывая, что , включим в список ситуацию вида . После этого шага списки ситуаций будут выглядеть следующим образом:

Выполняем шаг 5 алгоритма. Для ситуации осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Всего таких ситуаций две: и . Для каждой такой ситуации в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленные в список ситуации. Рассмотрение ситуации ничего не дает. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуация одна: . Для нее в список включаем следующую ситуацию: . После этого шага списки ситуаций будут выглядеть следующим образом:

Рассматриваем добавленную в список ситуацию. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуаций две: и . Для них в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя. Построение списков закончено. Так как ситуация , то цпочка принадлежит языку, порождаемому заданной грамматикой .

Дата добавления: 2014-01-07