46. Задача анализа автоматов-распознавателей.

Задача анализа автомата состоит в том, чтобы для конкретного автомата найти язык, распознаваемый этим автоматом.

Опишем алгоритм, использующий квадратные матрицы r-го порядка С₀, С₁, С₂, …, С_r(гдеr– число состояний автомата), элементами которых являются регулярные выражения. Элементы матрицы С_kобозначим через. Для каждой пары (i,j), гдеi,j= 1, 2, …,r, элементматрицы С₀– это множество тех символов входного алфавита А, каждый из которых за один такт переводит автомат из состоянияv_iв состояниеv_j. Поскольку это множество конечно, томожно задать регулярным выражением. Элементы матриц С₁, С₂, …, С_rбудем вычислять с помощью рекуррентного соотношения.

Из этого соотношения следует, что если все элементы матрицы С_k–1 – регулярные выражения, то матрица С_k тоже будет состоять из регулярных выражений. Можно строго доказать, что для любого k = 1, 2, …, r элемент представляет собой множество всех входных слов, переводящих автомат из состоянияv_i в состояние v_j за несколько тактов, но так, чтобы при этом автомат не проходил через промежуточные состояния, номера которых превосходят k. Если считать, что v₁ – начальное состояние автомата, а F – множество всех заключительных состояний, то язык L, распознаваемый этим автоматом, можно будет задать в виде суммы регулярных выражений, где суммирование ведется по всем заключительным состояниям автомата.

Пусть автомат, распознающий некоторый язык L, задан диаграммой Мура. Решив задачу анализа для этого автомата, мы получим регулярное выражение, задающее языкL. Спрашивается, каким регулярным выражением можно задать дополнительный язык? Рассмотрим два автомата, один из которых распознаетL, а другой –. Поскольку всякое слово из множества А* обязательно принадлежит одному из языковLили(но не обоим сразу!), то каждое слово распознается каким-либо одним этих автоматов, но не распознается другим. Следовательно, оба автомата задаются одинаковыми диаграммами Мура и имеют одно и то же начальное состояние. Отличаются они лишь тем, что каждое заключительное состояние одного из автоматов считается незаключительным состоянием для другого автомата. Поэтому, изменив набор заключительных состояний в диаграмме Мура, задающей автомат для распознаванияL, мы получим диаграмму автомата, распознающего. Например, если в автомате из примера 1, распознающем языкL, объявитьv₁начальным состоянием, аv₁иv₂– заключительными, то полученный автомат будет распознавать дополнительный язык. Затем, решив для него задачу анализа, найдем регулярное выражение для.