Теорема

Минимизация числа состояний ДКА

Алгоритм Томпсона

Преобразование регулярного выражения в КА

Теорема. Для любого регулярного выражения существует эквивалентный ему КА, то есть КА, задающий тот же язык, что и это регулярное выражение.

Следуем определению регулярного выражения

Базис

Индукция

Примечание.

КА, построенный этим алгоритмом, обладает следующими свойствами:

1. КА имеет ровно одно заключительное состояние;
2. Нет дуг, входящих в начальное состояние;
3. Нет дуг, исходящих из конечного состояния.

Пример

(0|1)*1(0|1) – преобразовать в НКА.

Для любого ДКА существует единственный эквивалентный ему ДКА с наименьшим числом состояний.

Определение. Строка различает состояния и , если, начиная работу из состояния после прочтения мы оказываемся в заключительном состоянии, а начиная с - в незаключительном (и наоборот).

Например, отличает любое заключительное состояние от незаключительного.

Дата добавления: 2013-12-14