Моделирование абстрактных автоматов




Скачать 109.09 Kb.
Дата14.07.2016
Размер109.09 Kb.
Санкт-Петербургский Государственный Морской Технический Университет

Курсовая работа на тему

«Моделирование абстрактных автоматов»

Выполнил: студент гр. 3270

Щеглов Г.

Проверил: Сиек Ю.Л.

Санкт-Петербург 2015

Содержание

1. Задание.

2. Введение.

3. Математическая модель конечного автомата.

3.1 Общая модель конечного автомата.

3.2 Граф автомата Мили.

3.3 Граф автомата Мура.

4. Эквивалентность автоматов.

4.1 Эквивалентность автоматов Мили и Мура.

4.2 Эквивалентность автоматов Мура и Мили.

5. Соединение автоматов.

5.1 Модель эквивалентного автомата. Общие формулы.

5.2 Пример заданного соединения.

6. Заключение. Связь конечного автомата с машиной Тьюринга.

7. Список Литературы

Задание № 15:

Заданы:


автомат Мили S1 автомат Мура S2

(начальное состояние ) (начальное состояние )





































Таблица переходов и таблица выходов соответственно Таблица переходов



















































Введение.

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

Математическая модель конечного автомата.

Рассмотрим абстрактный автомат, на вход которого в дискретные моменты времени t = =1,2,3..(автоматное время) подаются сигналы(символы входного алфавита). Автомат формирует на выходе сигнал (символ выходного алфавита). Одновременно изменяется внутреннее состояние, обозначаемое символом из заданного множества.



c:\users\asus\desktop\безымянный.jpg

Моменты t могут задаваться с помощью генератора тактовых импульсов(синхронный режим) или t соответствует моментам поступления входных сигналов(асинхронный режим).

Будем рассматривать асинхронный автомат. x(t) Ԑ X – входной алфавит, y(t) Ԑ Y – выходной алфавит,

a(t), a(t+1) Ԑ A – множество состояний.

Конечным называют автомат, у которого множество A конечно. Математическая модель абстрактного асинхронного конечного автомата задается кортежем S = > .
- начальное состояние автомата.

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

δ : A×X => A.

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

λ : A×X => Y.

Функции переходов и выходов называют законом функционирования автомата, которое описывает отображение ʋ : A×X => A×Y

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

Граф автомата Мили.

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

Граф автомата Мура.

В автомате Мура дуга отмечается выходным символом, а вершины выходным.

Представления соответственно:


c:\users\никита\desktop\новый точечный рисунок.bmp

Эквивалентность автоматов.


Эквивалентный автомат Мили и Мура.

Задан автомат Мили S1.























































На вход:



a2

a1

a3

a3

a2

a2

x1

x1

x2

x1

x2




y2

y1

y2

y1

y1




B = { b1 = a1y1, b2 = a2y1, b3 = a3y1, b4 = a1y2, b5 = a2y2, b6 = a3y2 }







b1

b2

b3

b4

b5

b6

x1

b3

b4

b2

b3

b4

b2

x2

b2

b2

b6

b2

b2

b6

На вход эквивалентного автомата Мура:




b2

b4

b3

b6

b2

b2

x1

x1

x2

x1

x2




y2

y1

y2

y1

y1



Эквивалентный автомат Мура и Мили.

Рассмотрим примеры эквивалентных переходов.

Задан автомат Мура S2.





































На вход:



b1

b1

b1

b2

b3

b3

x1

x1

x2

x1

x2




y1

y1

y3

y2

y2



Эквивалентный автомат Мили имеет вид:





















































На вход эквивалентного автомата:




b1

b1

b1

b2

b3

b3

x1

x1

x2

x1

x2




y1

y1

y3

y2

y2



Соединение автоматов.

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

Путем преобразования сеть может быть заменена эквивалентным автоматом. Таким соединением автоматов является – параллельное, последовательное, с обратной связью.


Модель эквивалентного автомата для заданного соединения.

Рассмотрим параллельное соединение автоматов S1 и S2. Структура соединения имеет вид:



i:\учеба\теория автоматов\структура параллельнгого соединения.jpg

Где «ϕ» - функциональный элемент реализующий отображение ϕ: Y1 × Y2 = > Y.

Соединение заменено эквивалентным автоматом S = < C, X, Y, δ, λ, Co >. Элементы которого определены как: C = A × B = { = × }, X=X1=X2, Y – выходной алфавит функционального элемента.

δ() = ((,) ,(,))

λ() = ϕ((,),,))

Ограничение на соединение – автомат S1 и S2 должны иметь одинаковые входные алфавиты.


Автомат S1:





















































Автомат S2:





































Функциональный элемент:


























Модель эквивалентного автомата S включает:

C = {C1= a1b1, C2 = a1b2, C3 = a1b3, C4 = a2b1, C5 = a2b2, C6 = a2b3, C7 = a3b1, C8 = a3b2, C9 = a3b3}

Xp = { X1 = = , X2 = = }

Y = (y1,y2,y3)

Co = a2b1 = C4







c1

c2

c3

c4

c5

c6

c7

c8

c9

x1

c7/y2

c9/y1

c7/y2

c1/y1

c3/y2

c1/y1

c4/y2

c6/y1

c4/y2

x2

c5/y2

c4/y2

c6/y1

c5/y2

c4/y2

c6/y1

c8/y2

c7/y1

c9/y2

Проверка


Подаем на вход автоматов S1, S2 и S слово : X2 X2 X1 X1

S1 S2


a2

a2

a2

a1

a3

X2

X2

X1

x1















b1

b2

b1

b1

b1

X2

X2

X1

x1















Используя функциональный элемент на выходе : y2 y2 y1 y2

S


c4

c5

c4

c1

c7

X2

X2

X1

x1




y2

y2

y1

y2




На выходе : y2 y2 y1 y2

Связь конечного автомата с машиной Тьюринга.

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

Список Литературы



Лекционный курс; [Электронный ресурс] // ru.wikipedia.org : свободная энциклопедия России // URL: https://ru.wikipedia.org/wiki/Maшина_Тьюринга


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница