Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 9 стр.

тельное состояние на графе обозначается двумя концентрическими окружно-
стями.
           Алгоритм 2.1. Построение КА по регулярной грамматике
     Вход: регулярная грамматика G = (VT , VN , P, S ) .
                      Выход: КА M = (Q, T , F , H , Z ) .
      Шаг 1. Пополнить грамматику правилом A → aN , где A ∈V N , a ∈VT и N
- новый нетерминал, для каждого правила вида A → a , если в грамматике нет
соответствующего ему правила A → aB , где B ∈VN .
      Шаг 2. Начальный символ грамматики S принять за начальное состояние
КА H . Из нетерминалов образовать множество состояний автомата
Q = V N ∪ {N } , а из терминалов – множество символов входного алфавита
T = VT .
      Шаг 3. Каждое правило A → aB преобразовать в функцию переходов
F ( A, a ) = B , где A, B ∈V N , a ∈VT .
       Шаг 4. Во множество заключительных состояний включить все вершины,
помеченные символами B ∈VN из правил вида A → aB , для которых имеются
соответствующие правила A → a , где A, B ∈V N , a ∈VT .
     Шаг 5. Если в грамматике имеется правило S → ε , где S - начальный
символ грамматики, то поместить S во множество заключительных состояний.
     Шаг 6. Если получен НКА, то преобразовать его в ДКА.
                   Алгоритм 2.2. Преобразование НКА в ДКА
     Вход: НКА M = (Q, T , F , H , Z ) .
     Выход: ДКА M ′ = (Q′, T , F ′, H , Z ′) .

     Шаг 1. Пометить первый столбец таблицы переходов M ′ ДКА начальным
состоянием (множеством начальных состояний) НКА M .
     Шаг 2. Заполняем очередной столбец таблицы переходов M ′ , помечен-
ный символами D , для этого определяем те состояния M , которые могут быть
достигнуты из каждого символа строки D при каждом входном символе x . По-
местить каждое найденное множество R (в том числе ∅ ) в соответствующие
позиции столбца D таблицы M ′ , т.е.:

            F ′( D, x) = {s | s ∈ F (t , x) для некоторого t ∈ D }.

     Шаг 3. Для каждого нового множества R (кроме ∅ ), полученного в
столбце D таблицы переходов M ′ , добавить новый столбец в таблицу, поме-
ченный R .
     Шаг 4. Если в таблице переходов КА M ′ есть столбец с незаполненными
позициями, то перейти к шагу 2.

                                                                         9