Математическая логика

конечных автоматов

= ,
где
S – конечное непустое

множество состояний;
X – конечное непустое множество входных сигналов (входной алфавит);
Y – конечное непустое множество выходных сигналов (выходной алфавит);
s0  S – начальное состояние;
δ: SX  S – функция переходов;
λ: SX  Y – функция выходов.

= ,
где
S – конечное непустое

множество состояний;
X – конечное непустое множество входных сигналов (входной алфавит);
Y – конечное непустое множество выходных сигналов (выходной алфавит);
s0  S – начальное состояние;
δ: SX  S – функция переходов;
λ: S  Y – функция выходов.

а)

б)

- Элементы алфавита V, как обычно, будем называть буквами.
-

Конечные последовательности (цепочки) букв (в том числе и пустая последовательность), называются словами в алфавите V (ясно, что пустое слово не содержит букв; будем обозначать его буквой ).
- Множество всех слов в алфавите V обозначается через V*.
Например, если V = {а, b, с}, то
V* = {, а, b, с, аа, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, ... }.
Очевидно, что хотя V конечно, V* – бесконечное счетное множество.
Любое множество слов в алфавите V называется языком над V. Язык над алфавитом V будем обозначать LV, ила просто L, если алфавит V фиксирован. Ясно, что множество L является языком над V тогда и только тогда, когда L есть подмножество множества V* , т.е. L V*.

δ, F),
где
S – конечное непустое множество состояний;
X  V*

– конечное непустое множество входных сигналов (входной алфавит);
s0  S – начальное состояние;
δ: S  X → S – функция переходов;
F  S – множество заключительных (финальных) состояний.

она является фундаментом большого числа разнообразных приложений. Эти приложения –

от языковых процессоров до систем управления реального времени и протоколов связи – покрывают значительную долю систем, разработкой, реализацией и анализом которых занимается информатика.

of the Future» 10 апреля 1994 года.
Brian Randell: «Я помню

Дуга Росса из компании SofTech, много лет назад говорившего, что 80 или даже 90 % информатики (Computer Science) будет в будущем основываться на теории конечных автоматов».
Herve Gallaire: «Я знаю людей из «Боинга», занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось сделать с помощью этой теории».
Brian Randell: «Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в OS UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы».