ФУНКЦИИ КОНЕЧНЫХ АВТОМАТОВ

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

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

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

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

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

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