Классификация конечных автоматов. До 50 минут

Приведем классификацию конечных автоматов по видам законов взаимодействия символов алфавитов A, Q, B, и по мощности последних.

1. В том случае, если S = Г, т.е. U=<A,Q,B,Г>, будем говорить о полном (всюду определенном) недетерминированном (в частности вероятностном, нечетком) автомате. При этом Dom Г = Q´A, ½Q´A½ = n*m; Im Г Í Q´B.
2. Если закон сопоставления элементов множеств Q´A и Q´B является однозначным (т.е. является функцией отклика S_f), то будем говорить о частном (не всюду определенном) детерминированном) автомате U=<A,Q,B,S_f>.
   В этом случае: S_f: Q´A ® Q´B, или S_f = <d,l>, где d: Q´A ® Q, l: Q´A ® B.
   Dom S_f Ì Q´A, ½ im q_ia_j ½ £ 1, q_iÎQ, a_jÎA.
   Итак, U=<A,Q,B,d,l> есть модель частичного по переходам и выходам детерминированного конечного автомата, в котором d- функция переходов (часто будем писать d(q_ia_j) = q_l,
   где q_i,q_l ÎQ), а l - функция выходов (будем писать l(q_ia_j) = b_p, b_p Î B).

Замечание:

1. говоря, что автомат является частичным детерминированным по переходам если:
   d:Q´A®Q, Dom S_fQÌQ´A;
   l:Q´A®B, Dom S_fb=Q´A;
2. говорят, что автомат является частичным детерминированным по выходам, если:
   d:Q´A®Q, Dom S_fQ=Q´A;
   l:Q´A®B, Dom S_fbÌQ´A;
3. Автомат называется асинхронным, если в нем для любых q_iÎQ и aÎA d(q_i, a_ia_j)=q_l. (nj есть такой автомат, который изменяет свое состояние при изменении входной буквы).
4. Всюду определенный детерминированный по переходам и выходам синхронный автомат (т.е. d(q_iaa_j)= d(d(q_ia),a_j), aÎA*,(в частности a=a_j, a_j,…a_j)) <A,Q,B, d,l> называется автоматом первого рода (автоматом Мили). Его функционирование часто записывают системой уравнений (рекуррентных соотношений)
   
   t= 1,2,3,...
   b_pÎB
   
   

Примечание:

a) функционирование автомата 2-го рода описывается системой рекуррентных соотношений
t= 1,2,3,...

b) для каждого автомата 2-го рода существует эквивалентный ему абстрактный автомат 1-го рода, функция выходов которого получается подстановкой функции переходов автомата 2-го рода в его сдвинутую функцию выходов, т.е.

c) конечный автомат называется автоматом Мура, если его функция выходов l:Q®B зависит только от состояний, т.е. для любых (m - функция отметок, т.к. она каждому состоянию однозначно ставит в соответствие отметку – выход В). Очевидно, что автомат Мура является частным случаем автомата 2-го рода:
t= 1,2,3,...

5. Конечный автомат называется функциональным (настроенным), если в Q выделено одно начальное состояние q₀. В этом случае такой автомат записывают в виде <U, q₀>, или
U =<A, Q, B, q₀, S>

6. Автомат Мили, выход которого зависит от внутреннего состояния (т.е. ), называется комбинационным (тривиальным, примитивным). В этом случае говорят, что множество Q есть множество эквивалентных состояний (все внутренние состояния эквивалентны).

Замечание. Минимальный комбинационный автомат, т.е. если , называют автоматом без памяти. Этот автомат записывают кортеlжом вида <A, B, l>. Поскольку в процессе функционирования состояние такого автомата изменяться не может, выходной символ зависит только от входного символа в данном такте, (т.е. и не зависит от ранее поступивших символов.

7. Автомат Мили называется автономным автоматом (автоматом без входов), если . Очевидно, что все входные слова в этом случае имеют вид .

8. Автономный автомат Мура <Q,B, d, l> называют генератором.

9. Автомат Мили называют логическим автоматом, если и .
Очевидно, что для детерминированного логического комбинационного автомата:

a) функция переходов d выращена, а его поведение однозначно определяется функцией выходов l с одним аргументом, т.е. ;

b) функция выходов есть система k - логических функций от m переменных (i-ая функция определяет значение i-ой компоненты в выходном векторе автомата).

10. Автомат Мили, в котором , называется акцептором (автоматом без выходов). Его запись <A,Q, d>. В частности автомат Мура можно рассматривать как автомат без выходов, поскольку его состояния отмечаются различным образом, т.е. <A, m,d>, (где m - функция отметок ).

11. Автомат Мили, в котором , называется автоматом без памяти (комбинационный автомат).

12. Конечный инициальный автомат называют:

a) преобразователем (трансформером), если он преобразует входные слова, т.е. A*®B*;

b) распознавателем (акцептором), если он распознает (принимает) входные слова , где , А – множество заключительных состояний;

c) генератором, если он порождает слова в алфавите В (это т.н. автомат без входа).

Лекция №3.

Дата добавления: 2015-12-01