12. Синтез схем в базисе функции Пирса.

Функция ИЛИ-НЕ.

13. Понятие конечного автомата, его состояния и эквивалентности.

Конечный автомат – это дискретный преобразователь информации, с конечным входным алфавитом X = {x₁, x₂, …, x_n}, с конечным выходным алфавитом Y = {y₁, y₂, …, y_n}, с конечным числом внутренних состояний S = {s₁, s₂, … s_n}, работа которого описывается двумя характеристическими функциями:

δ: x * S → S'

λ: y * S → Y'

Или, иначе:

S(t+1) = F_δ[X(t); S(t)] // функция переходов.

Y(t+1) = F_λ[X(t); S(t)] // функция выходов.

Т.е. его состояние в следующий момент времени зависит от входного слова и текущего состояния. А его выходное слово в следующий момент времени зависит от входного слова и текущего состояния.

В моменты срабатывания (такта) конечного автомата определяются либо принудительно с тактирующих сигналами генератора и это синхронно конечные автоматы, либо асинхронно конечные автоматы, такты которого задаются каким-то внешним событием.

Состояние конечного автомата – это класс эквивалентности его входных историй.

Эквивалентность предысторий выходных слов – одинаковое влияние двух предысторий на дальнейшее поведение автомата.

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

Y(t+1) = F_λ[S(t)]

S(t+1) = F_δ[X(t), S(t)]

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

Y(t+1) = F[X(t)]

Подробная теория:

Рассмотрим некоторое устройство, о внутреннем устройстве которого ничего неизвестно (так называемый чёрный ящик).

О его работе судят по его реакции на входные воздействия в виде выходных сигналов.

На каждый вход устройства из множества X может быть подан произвольный символ из конечного входного алфавита X = {x₁, x₂, … x_n}. На каждом выходе устройства … из конечного алфавита выходных символов Y = {y₁, y₂, …, y_n}. Считается что функционирование устройства происходит в дискретные моменты времени t₁, t₂, …, t_n. Совокупность символов поданных на все входы устройства в момент времени t образуют входное слово X(t) = {x₁(t), x₂(t), …, x_n(t)}. Аналогично, совокупность символов, на выходе устройства в момент времени t образует выходное слово Y(t) = {y₁(t), y₂(t), …, y_n(t)}. Результат преобразования (т.е. преобразование вход-выход) X(t) → Y(t) зависит не только от того, что подано на вход устройства в момент времени t, но и от того что происходило раньше, т.е. от истории преобразований входных слов.

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

Преобразователи информации такого типа называются автоматами.

Не смотря на конечность входного алфавита X, число входных историй бесконечно, хотя и счётно. Если автомат будет везти себя по-разному для каждой предыстории преобразования, то он должен будет иметь бесконечную память, чтобы помнить все предыстории.

Введём на множестве предысторий A отношение эквивалентности. Две предыстории A_i и A_j будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Следовательно, для своего функционирования, автомат должен помнить не всю предысторию, а лишь класс эквивалентности, к которому принадлежит та или иная предыстория. В том случае, когда число классов эквивалентности конечно, соответствующая математическая модель называется конечным автоматным преобразователем или просто конечным автоматом.

Таким образом, конечный автомат это дискретный преобразователь информации, на вход которого подаётся входное слово, а на его выходе формируется выходное слово, которое зависит как от входного слова, так и от текущего состояния конечного автомата. В моменты срабатывания (такта) конечного автомата определяются либо принудительно с тактирующих сигналами генератора и это синхронно конечные автоматы, либо асинхронно конечные автоматы, такты которого задаются каким-то внешним событием.

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

F в подмножестве множеств состояния автомата S

Кроме того, чтобы задать состояние автомата, нужно знать его начальное состояние s₀.

Таким образом, конечный автомат задаётся следующей семёркой:

KA = {X, Y, S, δ, λ, s₀, F}

X – Входное слово.

Y – Выходное слово.

S – Число внутренних состояний.

δ – Функция переходов.

λ – Функция выходов.

s₀ – Начальное состояние.

F – Финальное состояние.

Если заданы входной и выходной алфавиты и число внутренних состояний конечного автомата, то число его переходов зависит от n и k и будет определятся как n^kn. А число всех возможных комбинаций выходных символов зависит от m, n и k, и определяется как m^kn. Следовательно, общее число конечных автоматов с заданными алфавитами заданным числом конечных состояний с точностью определяется как nm^nk.

Автоматы такого рода называются автоматами Мил'и.

Конечный автомат является детерминированным устройством, т.к. его работа описывается однозначными соотношениями. Обобщением теории конечных автоматов является теория стохастических конечных автоматов, в которой детерминированные конечные автоматы является частным случаем.

В стохастических конечных автоматах, вместо однозначных соответствий, задаются только вероятности таких переходов и выходов.

[X(t), S(t)] → Y(t+1) → S(t+1)

Вероятность будет выглядеть вот так:

P = { Y(t+1) = F_λ[S(t)] }

P= { S(t+1) = F_δ[X(t), S(t)] }

Таким образом, конечный автомат может быть задан как конечным автоматом Мура, так и конечным автоматом Мили. Эти модели эквивалентны, и при описании автомата, не дают никаких преимуществ друг перед другом.