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

      1 Тема и цель лабораторной работы

      Лабораторная работа № 2.
      Тема: «Построение конечного автомата по регулярной
грамматике»

       Цель: - закрепить понятия «регулярная грамматика», «недетер-
минированный и детерминированный конечный автомат»;
             - сформировать умения и навыки построения конечного
автомата по регулярной грамматике и преобразования недетерминиро-
ванного конечного автомата к детерминированному конечному автома-
ту.

      2 Постановка задачи

      Дана регулярная грамматика G = ({A, B, C, S}, {a, b}, P, S), где
      Р:   1) S → aB | aA;
           2) A → aA | bC | b;
           3) B → bB | aC | a.

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




                                                                     Лист

                                                                     3

                                                                         47