Класс (n, p, q)-автоматов.

(n, p, q)-автоматом называют автомат Мили, множество промежуточных состояний которого содержит n состояний, входной алфавит p символов, а выходной q реакций.

| S | = n

| X | = p

| Z | = q

Мощность всех возможных (n, p, q)-автоматов оценивается числом:

N^{(n, p, q)} = (qn) ^pn.

Доказательство:

N_Z = q^np

| S | = n

| X | = p

| Z | = q

N_S = n^np

| S | = n

| S | = n

| X | = p

N^{(n, p, q)} = N_Z * N_S = q^np * n^np = (qn) ^pn

Мощность частично-определенного (n, p, q)-автомата N _ч.опр. = [( q + 1 )( n + 1 )]^pn.

Доказательство:

См. подобно описанному ранее, где ( + 1) – состояние неопределенно.

2. Класс явно-минимальных (n, p, q)-автоматов.

Явно-минимальным (n, p, q)-автоматом называют автомат, у которого для любой пары строк _i и _j ( где _i ≠ _j ) найдется хотя бы один символ _l такой, что реакции будут отличны друг от друга:

f_Z (_l, _i ) ≠ f_Z (_l, _j )

Явно-минимальным (n, p, q)-автоматом называют автомат, у которого любая пара строк в подтаблице реакций отлична друг от друга.

Мощность явно-минимального (n, p, q)-автомата составляет:

N _я.мин. ^{(n, p, q)} = n^np *  _{r = 0 .. ( n - 1)} [q^p – r].

Доказательство:

1 строка q^p

2 строка q^p – 1

:

n строка q^p – ( n – 1 ) = q^p – n + 1

N_Z = q^p * (q^p – 1) * … * (q^p – n + 1) =  _{r = 0 .. ( n - 1)} [q^p – r]

N_S = n^np

N _я.мин. ^{(n, p, q)} = N_Z * N_S = n^np *  _{r = 0 .. ( n - 1)} [q^p – r]

3. Класс явно-сократимых (n, p, q)-автоматов.

(n, p, q)-автомат называют явно-сократимым, если в нем найдется хотя бы одна пара строк _i и _j ( где _i ≠ _j ) лексико-графически совпадающие в полной таблице переходов или становящиеся таковыми после замены _i на _j (_i  _j).

Мощность явно-сократимого (n, p, q)-автомата составляет:

N _я.сокр. ^{(n, p, q)}  (qn)^pn – _{r = 0 .. ( n - 1)} [(qn)^p – r].

Доказательство:

1 строка (qn)^p

2 строка (qn)^p – 1

:

n строка (qn)^p – ( n – 1 ) = (qn)^p – n + 1

Мощность таблицы, у которой все строки различны: N` =  _{r = 0 .. ( n - 1)} [(qn)^p – r].

В этом множестве существуют строки лексико-графически различные, но способные быть приведенными к явно-сократимым. Таким образом:

N _я.сокр. ^{(n, p, q)}  N^{(n, p, q)} – N` = (qn)^pn – _{r = 0 .. ( n - 1)} [(qn)^p – r]

4. Класс изоморфных автоматов.

Изоморфными автоматами будем называть автоматы, которые могут быть получены путем переиндексации состояний автоматов (_i  _j)

Мощность изоморфных автоматов составляет N_изом.  n!

Задача 2:

пусть задан автомат Мили. Найдем соответствующее описание автомата Мура (и наоборот).

1. Мили  Мура: ( _j, _i )  (`_ij)

