2. Модель Мура:

Z	1	2	…	p
X \ S	`1	`2	…	`l
1	i	…	…	…
2	…	…	…	…
…	…	…	…	…
k	…	…	…	j

Задача 1:

существует некоторый текст. Необходимо посредством считывающего устройства определить имеется ли в тексте слово, начинающиеся с буквы «Т» и заканчивающееся буквой «К».

X` = {А, Б, В,… Я, _ }  X = {Т, К, _ , }, где  - любая другая буква;

Z = {0, 1};

S = {₀, ₁, ₂, ₃ }, где:

₀ – начальное состояние, новое слово;

₁ – последовательность «_ Т», возможно искомое слово;

₂ – последовательность не «_ Т», ждать новое слово;

₃ – последовательность «_ Т … К», проверить, является ли окончанием слова.

S \ X	Z v				S v + 1
	Т	К		_	Т	К		_
0	0	0	0	0	1	2	2	0
1	0	0	0	0	1	3	1	0
2	0	0	0	0	2	2	2	0
3	0	0	0	1	1	3	1	0

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

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

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

| S | = n

| X | = p

| Z | = q

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

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

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

S \ X	Z v	S v + 1
	| X | = p	| X | = p
| S | = n	| Z | = q	| S | = n

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].

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

S \ X	Z v				S v + 1
	1	2	…	k	1	2	…	k
1	q	q + 1	q + 2	q + 3	n	n + 1	1	n + 2
2	q	q + 1	q + 2	q + 3	n	n + 1	2	n + 2
…	…	…	…	…	…	…	…	…
i	q	q + 1	q + 2	q + 3	n	n + 1	j	n + 2
j	q	q + 1	q + 2	q + 3	n	n + 1	i	n + 2
…	…	…	…	…	…	…	…	…
l	…	…	…	j	…	…	…	j

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)

S\X	Z v			S v + 1
	1	2	1		2
0	0	1	1		2
1	1	1	0		1
2	1	0	2		0



Z	0	1	1	1	1	0
X \ S`	`10	`11	`12	`20	`21	`22
1	`11	`10	`12	`12	`11	`10
2	`21	`20	`22	`22	`21	`20