Дискретная математика для программистов

Программа - это последовательность команд, а именно,

, ,, .

Пример:



X	0	0	0

;

;

;

;

.

Проверим потактно результаты применения команд:

x	x	0	0	0
x	x	0	0	0
x	x+1	0	0	…
x	x+1	1	0	…
x	x+2	1	0	…
x	x+2	2	0	…
x	x+3	2	0	…
x	x+3	3	0	…

:

:

:

:

:

:

:

:

После окончания работы программы результат находится во втором регистре.

Данный пример показывает, что функция

является МНР-вычислимой.

Пример:

x	y	x	y	0	…

;

;

;

;

;

;

.

Пусть имеется множество

,

NxN - прямое (или декартово) произведение.

Если

 и , то , , .

Функцией называется однозначное отображение

, или

,

где .

Область определения - это подмножество , для которого определено отображение

: если ,

то функция называется частично определенной; если

,

то функция называется тотальной.

Функция называется частично вычислимой, если существует МНР-программа для её вычисления в области определения.

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

Функция называется вычислимой если:

- существует предикат, принимающий значение «истинно» в области определения и «ложно» вне её;

- функция является частично вычислимой.

Характеристическая функция предиката

Рассмотрим предикат . Его характеристическая функция - это такая функция , которая принимает значение 1, если

,

и 0, если

.

Предикат называется разрешимым, если его характеристическая функция вычислима.

3.3 Рекурсия

Понятие рекурсии связано с фамилиями таких ученых, как Клини и Черч. Клини ввел понятие частичной рекурсивной функции. Им высказана гипотеза: все частичные функции являются частично рекурсивными (эта гипотеза недоказуема).

В силу тезиса Черча вычислимость эквивалентна рекурсивности (этот тезис также недоказуем).

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

Функция является общерекурсивной или рекурсивной, если она частично рекурсивна и всюду определена.

Три простейшие функции теории:

1)

- функция, которая позволяет добавлять к аргументу единицу;

2)

- операция обнуления;

3)

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

Три простейшие операции теории:

1. Суперпозиция. Пусть заданы следующие функции:

,

,

,

.

Суперпозицией функции , построенной с помощью функции , называется функция от тех же аргументов

,

которая представляет собой следующее:

.

Пример 1. Заданы следующие функции:

;

;

;

.

Выполним суперпозицию:

.

Пример 2. Дана функция

.

Требуется представить ее в сокрашенном виде. Для этого введем отдельные функции:

.

Введем новое обозначение:

.

Исходная функция приняла следующий вид:

.

Обозначим , тогда

.

Введем следующие обозначения:

.

Тогда

.

2. Примитивная рекурсия. Пусть заданы следующие функции: - местная

; - местная ; - местная .

Построение примитивной рекурсии:

,

.

Замечание. В случае требуется некоторое уточнение:

;

…

.

Основная идея сводится к вычислению функции при значении аргумента на основании вычисления этой же функции при значении аргумента .

Основные функции являются рекурсивными.

Сложность состоит в подборе и .

Пример. Доказать, что функция

является примитивно-рекурсивной.

Пусть

, , ,

Тогда

;

;

.

Итак, функция

является примитивно-рекурсивной.

Построим рекурсивную функцию с помощью следующей конструкции:

;

;

;

;

;

;

.

3. -оператор. Рассмотрим функцию

.

В некоторых случаях

.

Корней может оказаться несколько. C помощью -оператора считается возможным реализовать следующую последовательность операций:

-

- находят все корни при заданном ;

- среди всех корней выбирают наименьший.

3.4 Вычислимость по Тьюрингу

Алану Тьюрингу принадлежит идея построения гипотетической вычислительной машины. Опишем основные положения формальной теории машины Тьюринга.

Считаются заданными:

1. Внешний алфавит

.

2. Внутренний алфавит

.

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

4. Управляющая головка. На каждом такте управляющая головка находится напротив некоторой ячейки.

Работа машины Тьюринга описывается набором команд, имеющих синтаксис

,

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

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

Гипотетическая машина Поста строится сходным образом.

Команды теории Поста называются приказами. Считаются заданными (выполнимыми) шесть приказов:

1. Записать 1 и перейти к приказу .

2. Записать 0 и перейти к приказу .

3. Сдвинуть вправо и перейти к приказу .

4. Сдвинуть влево и перейти к приказу .

5. Если в ячейке 1, то перейти к приказу .

6. Если в ячейке 0, то перейти к приказу .

Более детальное рассмотрение показывает, что машины Тьюринга и Поста эквивалентны.

Набор команд для преобразования слова называется Т-программой. Т-программа может быть задана двумя способами: табличным способом, который сводится к заполнению таблицы

	Внешний алфавит
Внутренний алфавит

и в виде потока команд.

Пример 1. Рассмотрим работу машины Тьюринга, заданную следующей таблицей:

	-	1
	П	П
	1П	П

Для состояния описание отсутствует, т.е. при достижении состояния работа машины Тьюринга завершается.

Итак, слово 111 преобразовалось в слово 1111. Это значит, что вычислимой по Тьюрингу является функция, прибавляющая к целому числу единицу.

Целью работы машины Тьюринга является преобразование некоторого исходного слова в заданное.

Пример 2. Построить Т-программу, с помощью которой слово «лето» преобразуется в слово «осень».

Внешний алфавит:

;



-	Л	Е	Т	О	С	Н	Ь	-
	ОП	СП	ЕП					ЬП

Синтез машины Тьюринга. Пусть надо решить несколько задач, для каждой из которых имеется Т-программа. Существует две возможности:

1) применить несколько машин Тьюринга (для каждой задачи);

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

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

К настоящему времени установлено, что для построения универсальной машины Тьюринга достаточно располагать четырьмя внутренними и шестью внешними состояниями.

4. КОНЕЧНЫЕ АВТОМАТЫ

4.1 Основные определения и способы задания

Основной рассматриваемый объект - конечный автомат (КА).

КА - это система (так называемая «пятерка»)

,

состоящая из таких объектов:

- =

- множество входных сигналов;

- =

- множество выходных сигналов;

- =

- множество внутренних состояний;

- - функция, которая отображает декартово произведение во множество внутренних состояний ;

- - функция, которая отображает декартово произведение во множество выходов .

Переход из одного состояния в другое осуществляется потактно. Пусть номер такта обозначен как t. Тогда

, , .

Таким образом,

- канонические уравнения для КА.

Пример. Если A и B - улицы, то

{нажатие кнопки},

{генератор сигнала переключателя светофора движения на перекрестке улиц A и В} (рис. 4.1).

Рис. 4.1. Перекресток

Внутренние состояния: - движение по улице A; - движение по улице B; - пешеходный переход после движения по улице A; - пешеходный переход после движения по улице B.

Пусть алфавит выходов содержит буквы А, Б, П, тогда

K	П	П	Б	А
Г	Б	А	Б	А

K
Г

Рис. 4.2 иллюстрирует графический способ задания автомата.

Рис. 4.2. Размеченный граф автомата регулирования перекрестка

Матричный способ заключается во введении матриц отношений и :

, где

, где

Тем самым заданы матрицы переходов

,

и матрицы выходов

, .

Автоматное отображение сигналов задается следующим образом:

- - поступает сигнал

;

- - поступает сигнал

;

- - поступает сигнал

.

При этом

.

Таким образом, получаем отображение входного слова

в выходное слово

,

а - расширенная функция перехода

.

Свойства автоматного отображения:

1) ;

2) .

Эти свойства называются свойствами (условиями) автоматности отображения.

Пример.

(рис. 4.3).



Рис. 4.3 Размеченный граф отображения

Контрольное задание

Построить граф автомата, классифицировать состояния, продемонстрировать внешнее поведение для слова длиной 20 (табл. 4.1).

Таблица 4.1 Варианты задания

Номер варианта

Номер варианта

1

4/1

2/2

1/1

1/1

2

4/2

2/1

4/2

2/1

4/2

4/2

4/1

1/2

2/1

1/2

2/1

2/1

4/2

1/1

4/2

4/1

3/2

2/1

2/2

2/1

3

1/1

3/1

2/1

1/2

4

1/2

3/1

1/2

4/1

2/2

3/1

1/1

1/1

3/1

1/1

1/1

4/1

3/1

3/1

4/2

3/2

3/2

1/1

1/1

2/2

5

4/2

4/1

4/2

1/2

6

3/1

1/2

2/2

1/2

1/2

4/2

2/2

2/2

4/2

2/1

4/1

4/1

3/2

1/1

4/1

3/2

4/2

1/1

2/1

3/1

7

3/1

3/2

4/1

2/2

8

2/1

3/1

4/2

3/1

2/2

4/2

3/1

1/2

1/2

4/1

3/1

3/1

4/1

2/1

3/2

3/1

4/1

4/1

3/1

1/1

9

4/2

4/2

4/2

2/2

10

2/2

3/1

2/1

1/1

3/1

2/2

2/1

2/2

3/2

2/2

4/2

4/2

3/1

2/2

2/1

4/1

2/2

3/1

4/2

4/1

11

4/1

2/1

3/1

3/1

12

4/2

3/2

4/1

3/1

2/2

2/2

3/1

2/2

1/2

3/2

4/2

2/1

1/1

1/1

4/1

3/2

4/1

3/2

4/2

2/2

13

1/2

1/1

2/2

1/2

14

4/2

3/1

2/1

3/2

4/1

2/1

1/2

1/2

3/2

3/1

1/1

1/2

3/2

4/1

3/1

1/2

4/2

4/1

1/1

1/1

15

1/1

1/2

3/1

1/2

16

4/2

3/1

3/1

1/2

1/1

1/1

1/2

4/1

4/2

3/2

1/1

3/2

1/2

2/2

4/2

3/2

4/1

3/2

4/1

3/2

17

3/2

4/2

1/2

2/2

18

4/1

3/2

1/1

3/1

4/1

1/2

2/2

1/2

2/2

3/1

3/1

2/1

3/1

3/1

1/1

2/2

4/2

1/2

1/2

1/1

19

1/2

2/1

1/1

3/1

20

1/2

2/2

2/1

3/2

3/2

3/1

1/2

3/1

3/1

4/2

3/2

3/1

3/2

1/2

2/1

2/1

2/2

2/1

2/2

4/1

21

1/1

1/2

4/1

4/1

22

3/2

1/2

2/2

4/1

4/1

1/1

4/2

4/1

4/2

4/1

1/2

3/2

3/1

4/2

4/2

3/1

3/2

2/2

2/1

2/1

23

3/1

4/1

2/1

4/1

24

4/1

2/1

3/2

2/1

3/1

1/2

4/1

4/1

4/1

2/1

3/1

2/1

2/1

1/1

2/1

2/2

4/1

3/2

1/2

2/1

4.2 Эквивалентность автоматов. Минимизация

Рассмотрим два автомата:

,

.

Состояния из множества автомата и соответственно из множества автомата В называются неразличимыми, если

.

Автоматы и называются неразличимыми, если для любого состояния

существует состояние

,

такое, что

,

и наоборот,

.

Рассмотрим изменения состояний и выходов автомата с изменением времени. На каждом такте подается входной сигнал (символ), преобразуется внутреннее состояние, возникает сигнал выхода. Рассмотрим следующий такт. Действия аналогичны:

, .

Итак, автомат преобразует слова (как и машина Тьюринга, частным случаем которой является конечный автомат).

Рассмотрим состояние автомата . Состояние называется достижимым из состояния , если существует такое слово , что

.

Достижимые состояния образуют класс достижимых состояний (рис. 4.4).

Рис. 4.4 Достижимое состояние (а) и класс достижимых состояний (б)

Рассмотрим два автомата

,

и состояния

.

Автоматы называются эквивалентными, если

Иными словами, автоматы называются эквивалентными, если для каждого состояния существует эквивалентное ему состояние автомата . Эквивалентные автоматы обладают одинаковым внешним поведением, т.е. на одинаковые входные слова выдают одинаковые внешние слова. Автоматы могут различаться сложностью внутренней структуры, например, мощностью множеств и . Среди всех эквивалентных автоматов имеется минимальный. Одной из основных задач является следующая: найти автомат, эквивалентный данному, но обладающий наименьшим количеством внутренних состояний. Такие задачи решаются последовательно путем выявления одного неразличимого состояния, двух неразличимых состояний,…, неразличимых состояний, которые объединяются в классы неразличимых состояний.

Пример:

Автомат

Состояния

Классы состояний

A

1

2

3

4

5

6

7

8

9

1,5,8

1

6/1

6/2

1/2

5/2

6/1

6/2

8/2

6/1

6/2

2,9

2

3/1

7/1

3/2

3/2

7/1

7/2

7/2

4/1

4/1

3,4,6,7

3

6/2

3/2

9/1

2/1

6/2

6/1

2/1

6/2

4/2

-

На начальном этапе отыскиваем классы -эквивалентных неразличимых состояний (при ):

A

Классы

1

5

8

2

9

3

4

6

7

1,5,8

1

6/1

6/1

6/1

6/2

6/2

Ѕ

5/2

6/2

8/2

2,9

2

3/1

7/1

4/1

7/1

4/1

3/2

3/2

7/2

7/2

3,4,7

3

6/2

6/2

6/2

3/2

4/2

9/1

2/1

6/1

2/1

6

Приходим к автомату, внутренние состояния которого отождествляются с найденными классами эквивалентных состояний:

	1	2	3	4
1	3/1	3/2	1/2	4/2
2	3/1	3/1	3/2	3/2
3	3/1	3/2	2/1	4/1

У полученного и исходного автоматов внешнее поведение одинаково.

Контрольное задание

Воспользовавшись данными, приведенными в табл. 4.2, выполнить следующее:

а) построить граф для каждого из заданных автоматов (рекомендуется использовать VISIO);

б) минимизировать автоматы, построить графы, проверить правильность минимизаций на словах длиной 20;

в) установить, эквивалентны ли заданные автоматы, проверить на слове длиной 20.

Таблица 4.2 Варианты задания

№

А

1

2

3

4

5

6

7

8

9

В

1

2

3

4

5

6

7

1

1

8/1

8/2

8/1

5/2

8/1

3/2

1/2

8/2

8/2

1

4/2

7/2

4/2

2/1

4/2

4/2

3/1

2

7/1

6/1

4/1

7/2

6/1

6/2

7/2

6/2

4/1

2

1/1

2/1

6/1

5/2

6/1

3/1

2/2

3

8/2

7/2

8/2

2/1

8/2

2/1

9/1

8/1

4/2

3

7/1

1/1

1/1

1/2

1/1

1/1

1/2

2

1

3/1

3/2

3/2

5/2

3/1

1/2

8/2

3/1

3/2

1

6/2

7/2

6/2

6/2

7/2

7/1

7/2

2

6/1

7/1

7/2

6/2

7/1

6/2

7/2

4/1

4/1

2

1/2

1/1

4/2

3/2

3/1

3/1

1/2

3

3/2

6/2

3/1

2/1

3/2

9/1

2/1

3/2

4/2

3

5/1

4/2

2/1

2/1

1/2

7/2

7/1

3

1

3/2

8/1

7/1

2/2

3/2

3/2

3/2

2/2

8/1

1

7/2

6/2

7/2

7/2

6/2

6/2

6/1

2

4/1

7/2

7/2

1/1

5/1

1/1

7/1

8/1

8/2

2

1/2

1/1

4/2

3/2

4/1

1/2

4/1

3

9/1

1/2

6/2

3/1

9/1

2/1

1/1

4/1

6/2

3

5/1

3/2

2/1

2/1

1/2

6/1

6/2

4

1

3/1

3/2

3/2

5/2

3/1

1/2

8/2

3/1

3/2

1

7/2

6/2

7/2

7/2

6/2

6/2

6/1

2

6/1

7/1

7/2

6/2

7/1

6/2

7/2

4/1

4/1

2

1/2

1/1

4/2

3/2

4/1

1/2

4/1

3

3/2

6/2

3/1

2/1

3/2

9/1

2/1

3/2

4/2

3

5/1

3/2

2/1

2/1

1/2

6/1

6/2

5

1

6/1

6/2

1/2

5/2

6/1

6/2

8/2

6/1

6/2

1

6/2

6/2

4/2

6/1

4/2

6/2

4/2

2

3/1

7/1

3/2

3/2

7/1

7/2

7/2

4/1

4/1

2

7/1

5/1

7/2

7/1

5/2

5/2

3/2

3

6/2

6/2

9/1

2/1

6/2

6/1

2/1

6/2

4/2

3

5/2

3/2

2/1

6/2

1/1

6/1

2/1

6

1

3/2

7/1

8/1

2/2

9/2

3/2

3/3

3/2

7/1

1

7/2

4/2

4/2

1/1

4/2

4/2

3/1

2

4/1

8/2

8/2

1/1

5/1

1/1

7/1

8/1

7/2

2

1/1

2/1

6/1

5/2

6/1

3/1

1/2

3

9/1

1/2

6/2

3/1

9/1

2/1

4/1

1/1

6/2

3

2/1

7/1

2/1

2/2

2/1

2/1

2/2

7

1

3/1

3/2

3/2

5/2

3/1

8/2

1/2

3/1

3/2

1

7/2

2/2

7/2

7/2

2/2

2/2

2/1

2

7/1

6/1

6/2

7/2

6/1

6/2

7/2

4/1

4/1

2

1/2

1/2

4/2

3/2

3/1

1/1

3/1

3

3/2

7/2

3/1

2/1

3/2

2/1

9/1

3/2

4/2

3

5/1

2/1

6/1

6/1

1/2

4/2

2/2

8

1

8/2

3/1

2/2

2/2

8/2

8/2

9/2

5/1

3/1

1

7/2

4/2

4/2

1/1

4/2

4/2

3/1

2

4/1

5/2

3/1

1/1

5/1

1/1

7/1

5/2

3/2

2

1/1

2/1

6/1

5/2

6/1

3/1

1/2

3

9/1

1/2

4/1

8/1

1/1

2/1

9/1

6/2

6/2

3

2/1

7/1

2/1

2/2

2/1

2/1

2/2

9

1

1/2

1/2

1/1

5/2

1/1

8/2

3/2

1/1

1/2

1

5/2

2/2

5/2

5/2

2/1

2/2

2/2

2

6/2

6/1

7/1

7/2

6/1

6/2

7/2

4/1

4/1

2

1/2

1/2

4/2

3/2

4/1

1/1

4/1

3

1/1

7/2

1/2

2/1

1/2

2/1

9/1

1/2

4/2

3

7/1

2/1

6/1

6/1

2/2

3/2

1/2

10

1

6/2

4/2

5/2

4/2

4/1

4/1

8/2

4/1

4/2

1

5/2

6/2

5/2

5/2

6/1

6/2

6/2

2

1/2

7/1

1/2

7/2

7/1

1/1

7/2

3/1

3/1

2

3/2

4/1

1/2

4/2

1/1

4/2

1/1

3

9/1

1/2

2/1

4/1

4/2

4/2

2/1

4/2

3/2

3

2/1

3/2

2/1

7/1

6/2

6/1

4/2

4.3 Автоматы Мили и Мура. Размеченные графы

Рассмотренные ранее автоматы - это классические автоматы Мили. Автомат Мура - это автомат, выходы которого зависят только от текущего состояния:

,

где

- алфавит входных сигналов;

- алфавит выходных сигналов;

, , .

Автомат Мура - частный случай автомата Мили.

Оказывается, для каждого автомата Мили существует эквивалентный ему автомат Мура. Для доказательства каждое из состояний расщепляется на несколько состояний, для каждого из которых выход зависит только от состояния, но не от входа.

При табличном задании автомата Мура вместо двух таблиц рассматривается одна, которая называется размеченной функцией перехода:

Несколько изменяется представление графа. Обозначение выхода ставится возле каждого узла (рис. 4.5).

Рис. 4.5 Графическое представление автомата Мура

4.4 Автоматные языки

Общая теория конечных автоматов сводится к анализу и синтезу автоматов. Анализ: по и изучить особенности внешнего поведения автомата. Синтез: по внешнему поведению построить функции и . Вторая задача значительно сложнее первой.

Частные случаи практически важных КА (конечных автоматов):

- сумматор;

- задержка

(автомат задержки - это автомат Мура);

- счетчик.

Автоматы подразделяются на преобразователи и распознаватели. Иногда вместо распознавателя употребляется термин «акцептор». Все предыдущие автоматы являлись преобразователями. В настоящее время одно из основных применений автомата - установление факта принадлежности подстроки данной строке.

Рассмотрим задачу: установить наличие в заданной строке слова «резец». Синтез соответствующего автомата начинается с построения графа (рис. 4.6).

Рис. 4.6 Граф распознавания заданного слова

По графу строим таблицу, описывающую работу автомата-распознавателя:

р	/0	н/0	н/0	н/0	н/0
е	н/0	/0	н/0	/0	н/0
з	н/0	н/0	/0	н/0	н/0
ц	н/0	н/0	н/0	н/0	н/1
S	н/0	н/0	н/0	н/0	н/0

Далее подаем некоторую строку. Подстрока считается выявленной, если на выходе появляется единица:



а	с	б	1	8	л	к	р	р	е	з	а	р	е	з	е	ц	у	-
-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	1	-	-

Полученные таблицы для реализации функции допускают сжатие путем составления массива номеров строк и столбцов, отличных от н/0. Количество операций имеет порядок длины слова при автоматном распознавании.

В качестве задания осуществить проверку наличия какого-нибудь слова (или предложения) в произвольно выбранном тексте. Например, рассмотреть исходный текст некоторой программы на алгоритмическом языке PASCAL и проверить наличие выражения «for I:= » в этом тексте.

Основной технический аппарат при изучении автоматных языков - акцепторы, автоматы-распознаватели. Распознаватели осуществляют выделение всех входных предложений, принадлежащих языку. Автоматные языки - очень узкий класс всех возможных языков.

Словарь - это конечное множество.

Элементы словаря - символы (буквы).

Предложение - все конечные последовательности символов из заданного словаря.

- множество всех цепочек, построенных по данному словарю.

Множество содержит бесконечное количество элементов.

Грамматика - конечный механизм задания языка.

Существует два вида грамматик - порождающая и распознающая: первая - это механизм, позволяющий строить все допустимые предложения, вторая - отсеивает из множества те предложения, которые не принадлежат языку.

Синтаксис - правила построения языка.

4.5 Возможности автоматов

Конечные автоматы позволяют избежать использования в программах, реализующих алгоритмы, условного оператора «if», а также операторов выбора (например, «case»). Поэтому «автоматный» стиль программирования предпочтителен при построении сложных программ. Рассмотрим несколько примеров, демонстрирующих преимущества использования автоматов в процессе решения некоторых задач.

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

	0	1	2	3	4	5	6
1	1/0	2/1	3/2	4/3	5/4	6/5	0/6

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

.

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



	0	1	2	3	4	5
0	0/-	0/-	0/-	0/-	0/-	0/-
1	1/0	2/1	3/2	4/3	5/4	0/5

Однако следует отметить, что счетчики рассмотренного типа не позволяют считать до бесконечности. Это ограничение принципиально для конечных автоматов. Однако данной схемы достаточно для реализации обычных электронных часов [1].

Счетчик является примером так называемых автономных автоматов, входной алфавит которых содержит единственный символ. Если считать, что в каждой вершине графа имеется один выход, причем выходной сигнал совпадает с номером состояния, то он является эквивалентом отношения порядка, а граф автономного автомата - это простой ориентированный граф [2, 3]. Для входного слова достаточной длины выходное слово автономного автомата содержит периодически повторяющееся подслово.

Проверка четности. Пусть входной алфавит содержит два символа - ноль и единицу. Требуется построить алгоритм, согласно которому на выходе повторяется входное слово, но после каждого подслова, содержащего три символа, должен быть вставлен символ «0», если количество единиц в подслове четно, и символ «1» в противном случае.

Прежде всего отметим, что выходной алфавит конструируемого автомата не может состоять только из нуля и единицы, так как количество символов во входном и выходном словах должно быть одно и то же (требование автоматности).

Это требование удовлетворяется введением такого выходного алфавита:

.

Выход после третьего символа состоит из двойки символов: «00», «01», «10», «11». Обозначим состояния автомата как «-», «0», «1», «00», «01», «10», «11», подразумевая под «-» стартовое состояние. После этого оказывается возможным построение автомата проверки четности в следующем виде:

	-	0	1	00	01	10	11
0	0/0	00/0	10/0	-/00	-/01	-/01	-/00
1	1/1	01/1	11/1	-/11	-/10	-/10	-/11

Выполним кодирование состояний и выходов, сопоставляя состояние «-» и номер 0, «0» - номер 1, «1» - 2, «00» - 3, «01» - 4, «10» - 5, «11» - 6; выход «0» и номер элемента алфавита 0, выход «1» и номер 1, «00» - 2, «01» - 3, «10» - 4, «11» - 5. Тогда таблица построенного автомата примет такой вид:

	0	1	2	3	4	5	6
0	1/0	3/0	5/0	0/2	0/3	0/3	0/2
1	2/1	4/1	6/1	0/5	0/4	0/4	0/5

Граф этого автомата изображен на рис. 4.7.

Отметим, что состояния 3 и 6 эквивалентны. Это же относится и к паре состояний 4 и 5. Поэтому в данном случае имеется возможность минимизировать найденный автомат, объединив состояния 3, 6 в класс 3 эквивалентных состояний, а классы 4, 5 - в класс 4. Минимизированный автомат, эквивалентный исходному, в таком случае можно изобразить графически (рис. 4.8) и в виде таблицы:

	0	1	2	3	4
0	1/0	3/0	4/0	0/2	0/3
1	2/1	4/1	3/1	0/5	0/4

Если поставлена задача проверить четность в словах длиной n, то граф неминимизированного автомата будет содержать вершин, а минимизированного - .

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

Рис. 4.7 Граф автомата проверки четности

Рис. 4.8 Минимизированный автомат проверки четности

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

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

Учитывая, что слагаемые можно переставлять, кодировщик представим в виде матрицы X:



	0	1	2
0	0 (0+0)	1 (0+1)	2 (0+2)
1	1 (1+0)	2 (1+1)	3 (1+2)
2	2 (2+0)	3 (2+1)	4 (2+2)

Например, пара цифр (1,2) кодируется как элемент X[1,2] = 3, как и пара цифр (2,1). Автомат суммирования может быть задан в виде матрицы :

	0	1
0	0/0 (0+0 = 0·3 + 0)	0/1 (0+1= 0·3 + 1)
1	0/1 (1+0 = 0·3 + 1)	0/2 (1+1= 0·3 + 2)
2	0/2 (2+0 = 0·3 + 2)	1/0 (2+1= 1·3 + 0)
3	1/0 (3+0 = 1·3 + 0)	1/1 (3+1= 1·3 + 1)
4	1/1 (4+0 = 1·3 + 1)	1/2 (4+1= 1·3 + 2)

Собственно, сложение производится поразрядным (начиная с младшего разряда) пропусканием двух слов a и b (т.е. чисел, представленных в троичной системе счисления) через цепочку (рис. 4.9).

Рис. 4.9 Автоматное суммирование

Достоинством автоматного суммирования является то, что все действия ограничиваются нахождением элементов матриц X и А.

Автоматное декодирование. Рассмотрим основную идею на примере. Пусть задана таблица кодов, получаемых как пути в дереве (рис. 4.10). С движением от узла влево сопоставим символ «а», прямо - «б», вправо - «в». Таблица кодов имеет следующий вид:



Р	а	Т	ва	Л	бба
К	ба	Ы	ббб	С	вб
О	бв	У	вв	М	ббв

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

Рис. 4.10 Дерево кодирования

Выходной алфавит содержит буквы, соответствующие листам, а также пустой символ «-». В результате получаем таблицу автомата следующего вида:

	0	1	2	3
а	0/Р

Подобные документы

• Дискретная математика

  Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
  
  учебное пособие [702,6 K], добавлен 29.04.2009
  

• Минимальные формы булевых многочленов

  Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.
  
  курсовая работа [64,7 K], добавлен 12.05.2009
  

• Функционально полные системы булевых функций

  Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
  
  учебное пособие [1,3 M], добавлен 20.08.2014
  

• Дискретная математика в задачах

  Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
  
  учебное пособие [1,5 M], добавлен 27.10.2013
  

• Алгебра логики

  Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
  
  реферат [63,3 K], добавлен 06.12.2010
  

• Логика на словах

  Этапы развития логики. Имена ученых, внесших существенный вклад в развитие логики. Ключевые понятия монадической логики второго порядка. Язык логики предикатов. Автоматы Бучи: подход с точки зрения автоматов и полугрупп. Автоматы и бесконечные слова.
  
  курсовая работа [207,1 K], добавлен 26.03.2012
  

• История развития математической логики

  История возникновения и развития математической логики как раздела математики, изучающего математические обозначения и формальные системы. Применение математической логики в технике и криптографии. Взаимосвязь программирования и математической логики.
  
  контрольная работа [50,4 K], добавлен 10.10.2014
  

• Полные системы булевых функций

  Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
  
  курсовая работа [278,1 K], добавлен 21.02.2009
  

• Элементы математической логики. Исчисление высказываний

  Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
  
  контрольная работа [34,3 K], добавлен 12.08.2010
  

• Дискретная математика

  Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
  
  контрольная работа [740,3 K], добавлен 09.03.2015
  

• Теорема Силова

  Доказательство первой, второй и третей теоремы Силова. Описание групп порядка pq. Смежные классы по подгруппе и теорема Лагранжа. Классы сопряженных элементов. Нормализатор множества в группе. Теоремы о гомоморфизмах. Примеры силовских подгрупп.
  
  курсовая работа [246,9 K], добавлен 21.04.2011
  

• Идеальное - реально

  Сущность и методологические проблемы математической физики. Особенности математического моделирования жёсткости прокатного калиброванного валка. Основные положения и свойства идеальной математики. Порядок устройства и структурные элементы идеальных чисел.
  
  доклад [350,5 K], добавлен 10.10.2010
  

• Отношение эквивалентности

  Определение, типы и примеры отношений, способы их задания; алгебраическая и геометрическая интерпретации. Разбиение на классы и фактор-множество. Смысл отношения эквивалентности. Теорема о равносильности определений. Отношения в школьной математике.
  
  курсовая работа [1,0 M], добавлен 01.10.2011
  

• Полином Жегалкина

  Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
  
  курсовая работа [701,9 K], добавлен 27.04.2011
  

• Греко-китайская теорема об остатках

  Формулировки и доказательства китайской теоремы об остатках. Доказательство с помощью метода математической индукции. Конструктивный метод доказательства. Основные алгоритмы поиска решения. Применение китайской теоремы об остатках к открытию сейфа.
  
  курсовая работа [1,0 M], добавлен 08.01.2022
  

• Степенные ряды

  Определение степенного ряда. Теорема Абеля как определение структуры области сходимости степенного ряда. Свойства степенных рядов. Ряды Тейлора, Маклорена для функций. Разложение некоторых элементарных функций в ряд Маклорена. Приложения степенных рядов.
  
  реферат [89,3 K], добавлен 08.06.2010
  

• Некоторые интерполяционные свойства конечномерных сетевых пространств и пространств Лоренца

  Основные понятия и некоторые классические теоремы теории интерполяции. Определение общих свойств пространств Лоренца. Понятие нормы и спектрального радиуса неотрицательных матриц. Исследование интерполяционных признаков семейств конечномерных пространств.
  
  курсовая работа [289,9 K], добавлен 12.01.2011
  

• Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

  Функціональна повнота системи функцій алгебри логіки. Клас самодвоїстих функцій і його замкненість. Леми теореми Поста. Реалізація алгоритму В середовищі програмування С#, який визначає чи є система функцій алгебри логіки функціонально повна, вид повноти.
  
  курсовая работа [388,6 K], добавлен 17.05.2011
  

• Двумерная кластеризая по предельному расстоянию. Дискретная математика

  Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
  
  курсовая работа [362,9 K], добавлен 24.11.2010
  

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

  Описание абстрактных, структурных и частичных конечных автоматов. Работа синхронных конечных автоматов, содержащих различные типы триггеров, определение сигналов их возбуждения. Пример канонического метода структурного синтеза. Схема дверного замка.
  
  учебное пособие [19,6 M], добавлен 07.06.2009
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам