Этапы для заданной автоматной грамматики.

1. Этап

Преобразование автоматной грамматики.

Ac

AcZ (AZc) Z – конец

1. К грамамтики добавляется нетерминальный символ Z, который называется конечным.

2. Правила вида Ac, гдеA- нетерминальный символ, аc– терминал, заменяют на правилаAcZилиAZcв зависимости от того левосторонняя или правосторонняя грамматика.

3. Вводят дополнительное правило ZE, гдеEпустой символ, который относят кнетерминальным.

2. Этап

Построение графа автомата и разметка.

1. Ставим в соответствие каждому нетерминальному символу вершину графа, который помечается этим символом.

Для каждого правила AcB,AB– нетерминал,c– терминальный символ ставится в соответствие дуга между вершинамиAиB, которые помечаются символомc