Введение в схемы, автоматы и алгоритмы



             

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


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

Пусть 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. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.




Содержание  Назад  Вперед