Минимизация конечных автоматов

См. вопрос 30

18. Определите, есть ли бесполезные символы в следующей грамматике, и, если они есть, постройте приведенную грамматику….

Нетерминал называется порождающим (generating), если из него может быть выведена конечная терминальная цепочка. Иначе он называется непорождающим.

Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.

1. Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.

2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.

3. Если на шаге 2 множество изменилось, повторить шаг 2.

4. Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

Пример

Рассмотрим грамматику:

1. Возьмём множество, состоящее из единственного элемента: .

2. Из достижимы нетерминалы , , и . Добавим их в множество и получим .

3. Множество изменилось. Переберём заново правила из грамматики. Из можно вывести и , добавим их в множество.

4. Снова переберём правила. Из можно вывести только терминал, а нету в множестве.

5. После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: .

6. Теперь удалим правило , так как оно содержит в левой части нетерминал, которого нет в полученном множестве.