Автомати, які мають заборонені вхідні слова, називаються частковими

Наприклад, в таблиці 4 наведений автомат, в якому при стані а ₀ неповинна поступати буква x оскільки перехід із стану а при дії букви x не визначений. Спочатку повинна поступати буква x , яка переведе автомат із стану а в стан а , і тільки потім буква x₂.

З цього слідує, що вхідне слово повинне починатися тільки буквою x₁, а всі слова, що починаються буквою x , повинні бути виключені з вхідних.

Таблиця 4 - Переходи часткового автомата Милі

Крім того, як випливає з таблиці переходів, заборонені вхідні слова, в яких після змінної x , що привела автомат в стан а йде змінна x .

Побудуємо дерево переходів часткового атомата, заданого таблицею 4, для чотирибуквених слів (див. рис.1).

Малюнок 1 - Дерево переходів часткового автомата Милі

В таблиці 5 представлені всі можливі дозволені і заборонені вхідні слова часткового автомата, заданого деревом переходів часткового автомата на мал. 1.

Всіх вхідних слів автомата 2⁴ = 16, серед яких 6 дозволених, а інші 10 – заборонені.

При синтезі в часткових автоматах звичайно проводиться їх довизначення так, щоб автомат містив якомога менше елементів і тому їх синтез звичайно складніший, ніж повних.

Таблиця 5 - Вхідні слова часткового aвтомата

	Дозволені слова	Заборонені слова

Дата добавления: 2015-05-09