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

Определение. Детерминированный конечный автомат (ДКА) [48]- это пятерка ,где

• Q- конечное множество состояний;

• Σ- конечное множество входных воздействий;

• δ: Q?Σ → Q- функция переходов.

и входной символ, на выходе выдает следующее состояние;

• s є Q- начальное состояние;

• T c∑ Q- множество допускающих состояний.

Приведем теперь неформальное определение. Детерминированный конечный автомат состоит из бесконечной ленты с символами, считывающей головки и состояний с переходами. Набор символов на ленте называется алфавитом ДКА, а последовательность символов - словом. ДКА либо допускает слово, либо не допускает. Каждый переход помечается одним из символов алфавита. Считывающая головка движется по ленте только в одну сторону. ДКА стартует из начального состояния. Каждую итерацию ДКА делает следующее:

1. Считывает очередной символ с ленты.

2. Если из текущего состояния существует переход, помеченный считанным символом, то ДКА переходит по нему.

3. Если перехода нет, то ДКА не допускает слово на ленте (переходит в недопускающее состояние) и завершает работу.

4. Если ДКА переходит в допускающее состояние, то он допускает слово.

1.2.