дискретная-математика - Индуктивное определение функций перехода выхода

За этой фразой на самом деле не скрывается ничего глубокого. Я попробую объяснить суть "на пальцах". Что такое конечный автомат? Это такая картинка со стрелочками. Каждая стрелочка идёт от одной вершины к другой. Вершины называются состояниями (можно считать, что они пронумерованы), а стрелочки называются переходами. На каждой стрелочке написано две буквы -- обычно в виде $%x/y$%, где верхняя буква называется входной, а нижняя -- выходной.

Как работает такой автомат? Изначально он находится в некотором указанном состоянии - например, в первом. Далее на вход автомата подаётся последовательность букв (символов). Автомат их как бы читает по одной, и выполняет установленные действия. Прочитав букву $%x$% (из заданного заранее алфавита), он ищет стрелочку, на которой сверху написано $%x$%. Такая стрелочка должна быть всего одна, согласно условию. (Если их несколько, то это соответствует более сложному понятию недетерминированного автомата, которое в данной ситуации лучше не рассматривать.) Далее автомат смотрит, что написано на этой стрелочке под буквой $%x$%. Там расположена какая-то буква $%y$% (возможно, совпадающая с $%x$%), которую он должен выдать на печать на первом шаге своей работы. После чего автомат переходит по данной стрелочке, переходя в некоторое другое состояние. В принципе, стрелочка может быть "круговой", то есть отсылать к тому же самому состоянию -- в частном случае.

Теперь автомат оказался в состоянии $%q_i$%, и он рассматривает вторую букву, поданную ему на вход. И с ней выполняет аналогичные действия, то есть ищет переходную стрелку с данной буквой, печатает символ, под ней стоящий, и переходит по стрелке в новое состояние. Шагов будет сделано столько, какова была длина поданного на вход слова (то есть последовательности букв). На выходе будет напечатано слово такой же точно длины.

Индуктивные (то есть, фактически, пошаговые) определения здесь могут быть связаны с тем, что надо предъявить явные формулы зависимости выходного слова от входного. Для этого надо ввести ряд обозначений.

Прежде всего, автомат может быть задан таблицей, по которой мы определяем, что он должен делать, если находится в состоянии $%q_i$%, и на вход подан символ $%x$%. Он должен при этом перейти в состояние $%q_j$%, однозначно зависящее от $%q_i$% и $%x$% (или от $%i$% и $%x$%, если кому-то больше нравится), а также напечатать символ $%y$%, также зависящий от $%q_i$% и $%x$% однозначно. Тем самым, нам даны две функции, которые могут в книгах или в лекциях обозначаться как угодно, но я их сейчас обозначу через $%f$% и $%g$%. У нас получается, что эти функции задают следующее состояние $%q_j=f(q_i,x)$% и следующую выдаваемую на печать букву $%y=g(q_i,x)$%.

Пусть теперь функции $%f$%, $%g$% зафиксированы, а на вход подано слово $%x_1x_2\ldots x_n$%. Автомат работает по заданному алгоритму, и на выходе печатает слово $%y_1y_2\ldots y_n$%. Требуется написать явный вид формул, по которым эти "игреки" выражаются через все остальные данные.

Те состояния, в которых находится автомат в процессе своей работы, я обозначу через $%r_1$%, $%r_2$%, ..., $%r_n$%. Нам среди них известно только самое первое, а все остальные находятся пошагово по следующим формулам:

$%r_1=q_1$%

$%y_i=g(r_i,x_i)$% (для всех $%i$% от $%1$% до $%n$%)

$%r_{i+1}=f(r_i,x_i)$% (для всех $%i$% от $%1$% до $%n$%, но случай $%i=n$% можно при желании не включать, если нам не важно, в каком состоянии автомат будет находится в конце работы)

Введённые здесь мной обозначения не являются стандартными -- я выбрал первые попавшиеся с целью пояснения.