Модель Мура:
Z | 1 | 2 | … | p |
X \ S | `1 | `2 | … | `l |
1 | i | … | … | … |
2 | … | … | … | … |
… | … | … | … | … |
k | … | … | … | j |
Задача 1:
существует некоторый текст. Необходимо посредством считывающего устройства определить имеется ли в тексте слово, начинающиеся с буквы «Т» и заканчивающееся буквой «К».
X` = {А, Б, В,… Я, _ } X = {Т, К, _ , }, где - любая другая буква;
Z = {0, 1};
S = {0, 1, 2, 3 }, где:
0 – начальное состояние, новое слово;
1 – последовательность «_ Т», возможно искомое слово;
2 – последовательность не «_ Т», ждать новое слово;
3 – последовательность «_ Т … К», проверить, является ли окончанием слова.
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)-автоматов.