Функции конечных автоматов

Очевидно, что если в последовательные моменты времени

t ₀, t ₀ + 1,..., t ₀ + k,...

на вход автомата A поступают символы a _{i 1},..., a _{i k}, то с помощью уравнений (1) - (3) можно определить последовательность символов на выходе автомата в процессе переработки указанных входных символов, а также последовательность состояний автомата в процессе работы.

Пусть A = { a ₁,..., a _m } - некоторый алфавит. Словом в этом алфавите называется всякая конечная последовательность: a _{i 1},..., a _ik, все элементы которой являются символами из A.

Введем в рассмотрение пустое слово, которое не содержит символов, и обозначается как L.

Длиной произвольного слова называется количество символов в нем. Длина произвольного слова обозначается как | |.

Для обозначения множества слов в алфавите A применяется обозначение A ^*.

Пусть , Î A ^*. Тогда запись обозначает слово, получаемое последовательным выписыванием сначала символов слова , а затем символов . Слово называется сцеплением слов и .

Если Â = (A, B, Q, j, y) - это некоторый автомат, то всякое слово A ^* называется входным словом для Â.

Дата добавления: 2015-03-31