Введение в схемы, автоматы и алгоритмы



             

Автоматы для регулярных языков


Покажем, что каждый регулярный язык можно распознать конечным автоматом.

Теорема 5.1. Для каждого регулярного выражения r можно эффективно построить такой недетерминированный конечный автомат M, который распознает язык, задаваемый r, т.е. LM= Lr.

Доказательство Построение автомата M по выражению r проведем индукцией по длине r, т.е. по общему количеству символов алфавита ?, символов

и ?, знаков операций +, ?, * и скобок в записи r.

Базис. Автоматы для выражений длины 1:

, ? и a
? показаны на следующем рисунке.


Рис. 5.1. 

Заметим, что у каждого из этих трех автоматов множество заключительных состояний состоит из одного состояния.

Индукционный шаг. Предположим теперь, что для каждого регулярного выражения длины

k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное регулярное выражение r длины k+1. В зависимости от последней операции оно может иметь один из трех видов: (r1 + r2), (r1 r2) или (r1)*. Пусть M1= <?, Q1, q01, {qf1}, ?1 > и M2= <?, Q2, q02, {qf2}, ?2 > - это НКА, распознающие языки Lr1 и Lr2, соответственно. Не ограничивая общности, мы будем предполагать, что у них разные состояния: Q1
Q2 =
.

Тогда НКА M= <?, Q, q0, {qf}, ? >, диаграмма которого представлена на рис. 5.2, распознает язык Lr =Lr1 + r2=Lr1

Lr2.


Рис. 5.2. 

У этого автомата множество состояний Q = Q1

Q2
{ q0, qf}, где q0 - это новое начальное состояние, qf - новое (единственное !) заключительное состояние, а программа включает программы автоматов M1 и M2 и четыре новых команды ?-переходов: ? = ?1
?2
{q0
q01, q0
q02, qf1
qf, qf2
qf}. Очевидно, что язык, распознаваемый НКА M, включает все слова из L{M1} и из L{M2}. С другой стороны, каждое слово w
LM переводит q0 в qf, и после первого шага несущий его путь проходит через q01 или q02. Так как состояния M1 и M2 не пересекаются, то в первом случае этот путь может попасть в qf только по ?-переходу из qf1 и тогда w
LM1}. Аналогично, во втором случае w
LM2.

Для выражения r = r1? r2 диаграмма НКА M= <?, Q, q0, {qf}, ? >, распознающего язык Lr, представлена на следующем рисунке.




Содержание  Назад  Вперед