Пример. (про АО см.10 вопр)

13. Сети и коллективы автоматов.

19. Конечный автомат – математическая модель дискретных объектов, в которых переход из одного состояния в любое другое может быть совершен за конечное число шагов.

Конечный автомат является частным случаем машины Тьюринга < A₁, Q₁, S>, а именно:

· внешний алфавит конечного автомата А₁=АÈ В, АÇ В=Æ, где А – входной алфавит, В – выходной алфавит;

· внутренний алфавит Q₁=Q (т.е. D={dл, dп, dн}=Æ);

соответствие S вход-выход конечного автомата Q´ A®Q´ B, Dom S Í Q´ A, Jm S Í Q´ B.

В этом плане конечный автомат U₃ = < A, Q, B, S> в общем случае (как трансдъюсер) является частичным (т.е. не всюду определенным) и недетерминированным.

Автомат U₃=< A, Q, B, Г>, где Г – отображения, будем называть всюду определенным недетерминированным конечным автоматом.

Автомат U₃=< A, Q, B, Г_f>, где Г_f – функциональное отображение, называется всюду определенным детерминированным конечным автоматом.

Далее будем рассматривать инициальные автоматы, в которых Г_f есть характеристические функции перехода d ивыхода l, т.е: U₃(q₀)=< A, Q, B, q₀, d, l>, q₀Î Q, d: Q´ A ® Q, l: Q´ A ® B

Напоминание:

1) Кортеж < A, Q, B, d, l> есть трансдьюсер, т.е. Г_f: А*®В*

2) Кортеж < A, Q, d> - акцептор (распознаватель), т.е. aÎ L (s₃)Ì А*, если `d(q₀, a)= q­_iq₀..q_z, q_zÎ Q, q_z – конечное состояние конечного автомата.

3)Конечный автомат называется комбинационным автоматом, если все его состояния Q эквивалентны между собой, т.е. b_e=l(q_i, а)= l(q_j, а) (выходной символ b_eÎ В не зависит от состояния автомата, а определяется только входным символом аÎ А). В свете этого определения минимальный (приведенный) комбинационный автомат, т.е. если |Q|=1, есть автомат без памяти < A, B, l>, для которого функция переходов d вырождена, а функция выходов имеет вид функции одного аргумента – l(a_i)= b_j, a_iÎ А, b_jÎ В

4) Конечный автомат, в котором А=В={0, 1}называют логическим.