Построение конечного автомата по регулярной грамматике

Цель работы:

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

Разработать программное средство, реализующее следующие функции:

1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принадлежность к классу регулярных грамматик;

2) построение по заданной регулярной грамматике конечного автомата;

3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату;

4) вывод графа результирующего конечного автомата на экран.

5

G=({K, L, M, N, Q, P, R, S}, {0, 1, *, $, /}, V, K), где V:

1) K®1L | 0N;  2) L®0M | 0P | /Q;  3) N®1R | 1M | *S;  4) Q®1P;    5) P®*L | $;  6) M®$;  7) S®0R;  8) R®/N | $.