Алгоритм определения пустоты языка

Определение пустоты языка

Приведение КС-грамматик

Алгоритм приведения состоит из шести шагов:

1. Определение пустоты языка, порождаемого КС-грамматикой;

2. Удаление недостижимых символов;

3. Удаление бесплодных (бесполезных) символов;

4. Удаление - правил (пустых правил);

5. Удаление цепных правил;

6. Если на предыдущих шагах алгоритма приведения грамматики произошло её преобразование, то шаги 2-5 повторить (хотя достаточно выполнить шаги 2 и 3).

Определение: Язык называется пустым, если множество его слов пусто.

Вход: КС-грамматика .

Выход: Если -выдать «НЕТ»;-выдать «ДА».

Метод:

1. ;

2. ;

3. Если , то переходим к шагу 4;

если , то и переходим к шагу 2;

4. Если , то язык не пуст и выдать «ДА»;

если , то язык пуст и выдать «НЕТ».

Пример:

.

Решение:

1. ;

2. ;

3. ;

4. ;

5. , алгоритм останавливается;

6. - «Нет» (пуст).

Ответ: язык пуст.

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