Определение НРС-автомата

У недетерминированных автоматов, при данном состоянии и данном входе (который м.б. последовательностью отдельных входов), состояние, которое должен принимать автомат, может быть определено неоднозначно. Автомат может выбирать между возможными переходами в следующее состояние. Такие автоматы могут изменять свое состояние спонтанно, то есть не получая никакого входа.

Определение. Конечный недетерминированный автомат Робина Скотта (НРС-автомат) есть пятерка A= (X, Z, t, S, F).

Здесь X и Z - конечные множества (входов и состояний соответственно), X также называют входным алфавитом автомата А.

S и F - подмножества множества Z (множества начальных и конечных состояний соответственно).

t: Z´F(x)®Z - многозначное отображение с конечной областью определения, называемое соответствием переходов.

Замечание: будем называть автомат А побуквенным, если он не имеет спонтанных переходов.

НРС-автомат А может быть представлен ориентированным взвешенным графом (см. пример). Такие графы иногда называют переходными системами. Если нужно реализовать автомат, как последовательную программу или прибор, то для такой реализации нужен детерминированный автомат с единственным начальным состоянием, в графе которого при любом входном слове существует не более одного пути из начального состояния в некоторое финальное состояние, определяемое этим словом.

Вопросы и упражнения

1. В чем отличие РС-автоматов от автоматов Мура и Мили?

2. Какой автомат называется недетерминированным?

3. Существует ли соответствие, не являющееся отображением? Приведите пример.

4. Какой автомат называется побуквенным?