Частичный недетерминированный конечный автомат

Теория автоматов

Конечные автоматы.

Конечный автомат – это кортеж U=<A, Q, B, S>, где

А – конечный входной алфавит мощностью m,

Q – конечный алфавит внутренних состояний мощностью n,

B – конечный выходной алфавит мощностью k,

S: Q x A → Q x B (Dom S Ì Q x A)

Частичный недетерминированный конечный автомат

Имеет вид

a=< a₁, a₂,, a_m>

b=<b₁,b₂,,b_k>

Замечания.

1. Автомат называется частичным, если некоторым парам из множества QxA не сопоставлены элементы из множества QxB.

2. Автомат называют недетерминированным, если закон сопоставления S не является однозначным.

3. Автоматная таблица определена не полностью (частично, не всюду), если некоторые ее клетки не заполнены.

4. В автоматной таблице недетерминированность автомата выражается в том, что в некоторых ее клетках стоят несколько состояний.

Дата добавления: 2015-07-10