14. Регулярные языки и конечные автоматы. Определение.

Любое автоматное отображение φ может быть задано конечным множеством М событий во входном алфавите этого отображения.

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

Для языка регулярных выражений алгебры событий используются три операции над событиями:

1) А∪В – объединение (дизъюнкция);

2) А⋅В – умножение (конкатенация);

3) {A} – итерация (обозначается также А*).

Определим конечные множества входных букв Х = {x₁, ..., x_n} и зададим для этого множества регулярное выражение.

Определение.

Регулярным выражением в алфавите Х называется выражение, построенное из букв алфавита Х и из символов операций объединения, умножения и итерации с использованием соответствующим образом круглых скобок.

Всякое регулярное выражение определяет некоторое событие S (событие S получается в результате выполнения всех операций, входящих в регулярное выражение). События, определяемые таким образом, называются регулярными событиями над алфавитом Х. Другими словами регулярным событием (или языком) называется событие, полученное из элементарных событий (однобуквенных слов x_i) применением конечного числа раз операций дизъюнкции, конкатенации и итерации.

Например, в алфавите из трех букв x, y, z регулярное выражение

x {x ∨ y ∨ z} (y ∨ z) задает регулярное событие, состоящее из всех слов, которые начинаются буквой х и заканчиваются буквой y или z. Для конечных автоматов характерны только регулярные события.

Определение.

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

Определение.

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

15. Основной алгоритм синтеза конечных автоматов.

Определение.

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

Перейдем от представления событий R₁,...,R_p в автомате Мура множествами состояний к представлению их множествами выходных сигналов. Для этого достаточно в качестве выходных сигналов взять различные подмножества заданного множества событий (R₁,…,R_p) и отмечать каждое состояние q автомата множеством тех событий, которые содержат слова, переводящие автомат из начального состояния в состояние q.

Если состояния, не представляют ни одного из заданных событий, то они отмечаются пустым множеством событий. Такой способ отметок состояний автомата Мура называется каноническим способом отметок.

Если исходные для алгоритма регулярных выражений R₁,…, R_p заданные регулярные события являются многочленами, то они заключаются в обычные (неитерационные) скобки. Это условие будет называться условием правильной записи регулярных выражений.