Произведение автоматов

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

Пусть M1 = <?, Q1, q01, F1, ?1> и M2 = <?, Q2, q02, F2, ?2> - два конечных автомата с общим входным алфавитом ?, распознающих языки L1 и L2, соответственно. Определим по ним автомат M= <?, Q, q0, F, ?>, называемый произведением M1 и M2 (M= M1 ? M2), следующим образом. Q= Q1 ? Q2 ={ (q, p) | q

Q1, p

Q2}, т.е. состояния нового автомата - это пары, первый элемент которых - состояние первого автомата, а второй - состояние второго автомата. Для каждой такой пары (q,p) и входного символа a

? определим функцию переходов: ?((q,p), a) = (?1(q,a), ?2(p,a)). Начальным состоянием M является пара q0= (q01, q02), состоящая из начальных состояний автоматов-множителей. Что касается множества заключительных состояний, то оно определяется в зависимости от операции над языками L1 и L2, которую должен реализовать M.

Теорема 4.1.

При F
= { (q,p) | q
F1 или p
F2 } автомат M= <?, Q, q0, F
, ?> распознает язык L = L1
L2.
При F
= { (q,p) | q
F1 и p
F2 } автомат M= <?, Q, q0, F
, ?> распознает язык L = L1
L2.
При F\ = { (q,p) | q
F1 и p
F2 } автомат M= <?, Q, q0, F\, ?> распознает язык L = L1 \ L2.

Доказательство этой теоремы непосредственно выводится из следующего утверждения.

Лемма 4.2. Для любых двух состояний (q,p) и (q', p') автомата M и любого входного слова w слово w переводит (q,p) в (q', p') в автомате M тогда и только тогда, когда оно переводит q в q' в автомате M1 и p в p' в автомате M2.

Лемма устанавливается индукцией по длине слова w.

Следствие4.1.1. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.

Содержание раздела