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

        Таблица 2.2 – Построение функции переходов для ДКА M ′

         Шаг          1         2          3          4         5       6        7
          F           S        A, B       A, N       B, N       A       N        B
          a          A, B      A, N        A          N         A       ∅        N
          b           ∅        B, N        N          B         N       ∅        B

      2.2 Во множество заключительных состояний автомата M ′ включим эле-
менты Z ′ = {( A, N ), ( B, N ), N } .
      2.3 Введем следующие новые обозначения состояний автомата M ′ :
(A, B)=С, (A, N)=D, (B, N)=E.
      2.4 Искомый ДКА определяется следующей пятеркой объектов:
Q′ = {S , A, B, C , D, E , N } , T = {a, b} , функция переходов задана таблицей 2.3,
H = {S } , Z ′ = {N , D, E} .
      Граф полученного ДКА представлен на рисунке 2.1 справа.

        Таблица 2.3 – Функция переходов для ДКА M ′

          F′        S        A        B          С          D       E   N
          a         C        A        N          D          A       N   ∅
          b         ∅        N        B          E          N       B   ∅

                    Постановка задачи к лабораторной работе № 2
      Разработать программное средство, реализующее следующие функции:
      1) ввод произвольной формальной грамматики с клавиатуры и проверка
ее на принадлежность к классу регулярных грамматик;
      2) построение по заданной регулярной грамматике конечного автомата;
      3) преобразование недетерминированного конечного автомата к детерми-
нированному конечному автомату;
      4) вывод графа результирующего конечного автомата на экран.
      Варианты индивидуального задания представлены в таблице 2.4.

Таблица 2.4 – Варианты индивидуального задания к лабораторной работе № 2

Вариант                               Регулярная грамматика

               G=({S, C, D}, {0, 1}, P, S), где P:
    1
               1) S→1C | 0D; 2) C→0D | 0S | 1; 3) D→1C | 1S | 0.

               G=({S, A, B, C}, {a, b, c}, P, S), где P:
    2
               1) S→aA | bB | aC; 2) A→bA | bB | c; 3) B→aA | cC | b; 4) C→bB | bC |a.



                                                                                     11