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

Задача синтеза состоит в том, чтобы для заданного языка Lпостроить (синтезировать) автомат, распознающий этот язык. Согласно основной теореме теории автоматов, такой автомат существует только тогда, когдаL– регулярный язык. Поэтому далее будем решать задачу синтеза в предположении, что исходный языкLзадан регулярным выражением.

Напомним, что диаграмма Мура детерминированного автомата удовлетворяет условию детерминированности, т.е. для любого символа входного алфавита А из каждой вершины должна выходить ровно одна дуга, помеченная этим символом. Далее нам потребуются ориентированные графы, напоминающие диаграмму Мура автомата-распознавателя, но не обязательно обладающие свойством детерминированности. Такие графы мы будем называть недетерминированными источниками. Недетерминированный источник отличается от диаграммы Мура тем, что из любой его вершины может выходить несколько дуг, помеченных одним и тем же входным символом, или не выходить ни одной дуги с этим символом. Кроме того, некоторые дуги источника могут быть пустыми, т.е. помеченными символом Λ. Устройство, описываемое недетерминированным источником, является недетерминированным автоматом. Его также будем называть недетерминированным источником (или просто источником). Очевидно, любой детерминированный автомат является источником, но не любой источник можно считать детерминированным автоматом из-за того, что в источнике может быть нарушено условие детерминированности. Источник, как и автомат-распознаватель, имеет одну начальную и одну или несколько заключительных вершин. Поэтому он тоже распознает некоторый язык.

ТЕОРЕМА.Если недетерминированный источник имеетnсостояний и распознает некоторый языкL, то найдется детерминированный автомат, который имеет не более 2ⁿсостояний и распознает тот же самый языкL.

Из этой теоремы следует, что недетерминированные источники способны распознавать только регулярные языки. Более того, теорема утверждает, что для любого источника найдется эквивалентный ему автомат, т.е. автомат, распознающий тот же самый язык. Иными словами, в области распознавания языков детерминированные автоматы умеют выполнять ту же самую работу, что и недетерминированные источники. Теорема об источнике дает нам метод для решения задачи синтеза автомата. Действительно, сначала по заданному языку можно построить недетерминированный источник (это сделать проще, чем сразу строить детерминированный автомат), а затем полученный источник надо «детерминизировать», т.е. преобразовать в эквивалентный ему детерминированный автомат.

Алгоритм построения источника по заданному языку опирается на тот факт, что для любого регулярного языка существует распознающий его двухполюсный источник, т.е. источник с одной начальной и одной заключительной вершинами. Это позволяет строить требуемый источник последовательным и (или) параллельным соединением более простых источников, распознающих отдельные множители и слагаемые, входящие в состав заданного регулярного выражения. А именно, пусть имеются два двухполюсных источника G₁иG₂, распознающие языкиL₁иL₂. Черезu₁,u₂иv₁,v₂обозначим соответственно их начальные и заключительные вершины. Параллельное соединение этих источников изображено на рисунке «а». Все добавленные дуги являются пустыми, т.е. помечены символомΛ. Добавленные вершины и иvявляются начальной и заключительной вершинами полученного источника соответственно. Очевидно, этот источник распознает сумму языковL₁+L₂.

Последовательное соединение двухполюсников G₁иG₂изображено на рисунке «б». При последовательном соединении добавляется пустая дуга, идущая из заключительной вершины первого источника в начальную вершину второго источника. В полученном источнике начальной вершиной являетсяu₁, а заключительной вершиной –v₂. Этот источник распознает произведение языковL₁· L₂.

Чтобы из двухполюсника G₁получить источник, распознающий итерацию языка (L₁)^*, необходимо выполнить следующие действия: добавить новые начальную и заключительную вершиныsиt; провести пустые дуги [s,t], [s, и₁], [v₁,u₁], [v₁,t]. В итоге получим двухполюсный источник с начальной вершинойsи заключительной вершинойt.

Поскольку всякое регулярное выражение представимо в виде суммы, произведения и итерации элементарных языков, то для распознавания любого регулярного языка можно построить источник с помощью последовательного и параллельного соединений более простых источников. После этого для решения задачи синтеза достаточно полученный источник преобразовать в детерминированный автомат, который существует в силу теоремы о недетерминированном источнике.

Определение.Подмножество вершин источникаGназывается замкнутым, если вместе с каждой вершинойvиз этого подмножества ему принадлежат также все вершины, в которые изvидет пустая дуга.