Частичные или не полностью определенные автоматы.

Пусть P= {P₀,P₁, … ,P_n} – входной алфавит

P^*- множество всех слов в алфавитеP

P^*_g – множество допустимых слов

P^*_g<=P^*

P^*_з=P^*/P^*_g - множество запрещенных слов

P^*иP^*_g – слова одной и той же длины

Автомат называется частичным, если

1. множество запрещенных слов не пусто или

2. на входное допустимое слово автомат вырабатывает выходное слово, в котором есть хотя бы одна буква, которой значение не важно, т.е.

P_{1 ,} P₁ , P₂ , P₁

W₀ , W₁ , * , W₀

, W₀ ,

, W₁ ,

Условие 1 приводит к тому, что в таблице переходов автомата будут прочерки – отсутствующие переходы.

Условие 2 приводит к тому, сто в значениях выходах таблицы будут находиться «*».

Пример :автомат Миля.

Pj	P1	P2	P3
Si
S0	S2/W1	---	---
S1	---	S2/*	S2/W2
S2	---	S0/W3	S3/W1
S3	---	S0/W1	S0/W3

В таблице присутствует как 1 так и второе условие.

P₁ / W₁

S₀

P₂ / *

P₃ / W₂

P₂ / W₃

P₂ / W₃

P₃ / W₁

Второе условие по графу видно явно, а первое нет.

Для проверки условия 1 нужно в каждой вершине проверить наличие переходов по каждой букве входного алфавита.

Так для состояния «S₀» есть переход только по P₁ и отсутствует P₂ и P₃