Шпора - Дискретная математика - файл n1.doc

приобрести
Шпора - Дискретная математика
скачать (105.4 kb.)
Доступные файлы (5):
n1.doc86kb.12.06.2003 18:32скачать
n2.doc87kb.11.06.2003 21:57скачать
n3.doc56kb.12.06.2003 18:40скачать
n4.doc202kb.11.06.2003 22:21скачать
shp_dm2.txt1kb.17.06.2003 18:29скачать

n1.doc

1.Алфавитные и автоматные отображения.Осн. понятия и опр.

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

Опр:Алфавит – это совокупность сигналов попарно различных.

Опр:Слово – конечная упорядоченная посл–ность символов алфавита.

Опр:Произведением слов p и q называется слово pq, полученное припbсыванием символов слова q к символам слова p. Буквой e обозн. пустое слово: ep=pe=p

Опр:Алфавитным отображением алфавита Х в алфавите Y называется всякое соответсвие между этими алфивитами, которое любому слову из алфавита Х сопоставляет слово из алфавита Y.

Опр:Автоматное отображение – такое алфавитное отображение, к-е удовлетворяет условиям:1. длина вх слова = длине вых.

2. ?(р,q)=?(p)r, ? – отображение, длина слова r = длине слова q. Если l1­–начальный отрезок слова l, то ?(l1)–начальный отрезок слова ?(l).

Если L1 есть начальный отрезок слова L, то ? от L1 есть начальный отрезок слова ?(L).

Автоматы работают в дискретный момент времени и для его работы задаются 3 алфавита и 2 функции

3 алфавита: 1) Х – {х1,.. хn} – вх алфавит 2) Y={y1… yn} – вых алфавит 3) Q={q1..qn}алфавит состояний

2 функции: 1) F – функция выхода; зависит от вх. сигнала и от состояния автомата в предыдущий момент времени t : x(t) q(t-1) 2)G – аналогично x(t) q(t-1)

Опр: Автомат наз. инициальным, если одно из его состояний выделено в качестве начального,неинициальным в противном случае.

Работу автомата описывают следующие канон. ур–ия:



где {x,y,Q,F,G,qo} – параметры.

Опр:Частичный автомат – если он задан не на всех парах XЧQ

Опр:Конечный автомат – если конечны алфавиты Q,X,Y
2.Реализация автоматных отображений автоматами. Способы задания автоматов. Автоматы Мили и Мура.

Пусть задано отображение ? алфавита Х в алфавит Y.

Опр: Допустимыми называются слова из области определения функций F и G.

Построим автомат, соответствующий отображению ?, при этом:

1)X/Y - входной/выходной алфавит.2)Q - множество всех допустимых слов.3)q0=e. 4)G(e,x)=ex. Были в состоянии е, подали х, состояние стало ех.5)F(e,x)=y, где ?(ex)=?(e)y. Были в состоянии е, подали х, получили у, где у - последний символ выходного слова.

Способы задания автомата:

1.Табличный.

Задаются таблицы для функции выхода и перехода следующим образом: X={x,y},Y={u,v},Q=(1,2,3},

G:




1

2

3

х

3

2

1

у

2

1

2

F:




1

2

3

Х

u

v

u

У

V

u

u

2.Диаграмма автомата.(+пример)

Заметим, что автомат задаваемый уравнениями (*) называется автоматом Мили. Распространение получили автоматы Мура:



Отличается тем, что выходной сигнал не зависит от входного. Описывается с помощью следующей таблицы:

X={x,y}, Y={u,v}, Q={1,2,3}




U

v

u

1

2

3

X

2

1

2

Y

3

3

2

Опр: Два автомата называются эквивалентными, если они реализуют одно и тоже автоматное отображение.Т: Для всякого автомата Мили существует эквивалентный ему автомат Мура.(+пример)
3.Минимизация полных автоматов методом Мили.Метод Шоломова.

Критерий минимума–число состояний автоматов–из всех эквивалентных автоматов выбираем тот, множество состояний которого содержит минимальное число автоматов.

I.МЕТОД МИЛИ.

1) К одной группе эквивалентных сост. относим сост. q и q’ в том случае когда для любого х из Х: F(q,x)=F(q’,x) для любого значения ф-ции выхода и любого входного сигнала совпадают.

2) На i+1 шаге в одну группу эквивалентных сост. относим сост. q и q’ i-ого шага относим в 1-у группу эквив. сост. в том случае когда значения выходов или совпадают или попадают в одну группу сост. i-го шага.

3) Минимизация заканчивается когда очередной шаг не вносит изменения в разбиение множества q.

II. МЕТОД ШОЛОМОВА.

1)Строим таблицу Шоломова;

2)Проводим первое вычеркивание клеток. Вычеркиваем те клетки у которых значения ф-ии выходов не совпадают (табл F:);

3)В пустые клетки выписываем пары сост. в которые перебрасывается автомат под действием входных сил, если пара совпадает с номером клетки её не пишем (табл. G:).

4)Проводим второе вычеркивание клеток при этом выч. те клетки в которых записаны номера уже вычеркнутых клеток;

5)Повторяем пункт 4 до тех пор пока это возможно, в результате получим пары эквив. сост. (это номера невычеркнутых клеток).

Заметим, что отношение эквивалентности транзитивно т.е. (a,b)^(b,c)=(a,c).
4.Минимизация полных автоматов с помощью Т алгоритма.

1. Находим все пары сов. и несов. состояний по табл. Шолохова.

2. Находим группировку: выписываем все состояний в порядке возрастания из номеров. Рассмотрим состояние q1. Вычеркиваем все сост., несовместимые с q1. Пусть номер первого невыч. сост. qi1. Выч. сост. несовместимые с qi1 и.т.д. В результате получим первую группу попарно совместимых состояний. Выписываем вычеркнутые номера последовательностей . Проделаем с ними то же, что и в первом пункте. Повторяем до получения группировки.

3. Проверим группировку на замкнутость, если круппировка замкнута, то к 5. , else 4.

4. Достраиваем группировку до замкнутой путем добавления некоторых состояний уже готовой группы или путем доб. некот. группы. совмест. 5. Стоим покрывающий автомат.

5.Синтез конечных автоматов. Минимизация частичных автоматов. Пример синтеза. Метод Шоломова.Минимизация частичных автоматов. Т-алгоритм.

Порядок синтеза автомата состоит в следующем:

1. По заданному отображению сост. физ. таблицу для f и q.

2. Проводим минимиз. автомата. 3. Проводим кодирование симв. алфавита и сост. канонич. табл. для 4. миним. б\ф с помощью карт Карнау. 5. сост. схему.

Пример:

1. e ; 2. a-u ; 3.ab-uv ; 4. ac-uw ; 5. abc – uvw; x={a,b,c} y={u,v,w} G{1-5}




1

2

3

4

5

a

2,u

-

-

-

-

b

-

3,v

-

-

-

c

-

4,w

5,v

-

-


2. (1,3,4,5) (7)

1 2





1

2

a1

2,u

-

a2

-

1,v

a3

1,v

1,w



3. Кодирование символов X: a-00 b-01 c-10 ; Y: u-00 v-01 w-10 ; Q: 1-0 2-1


g(t-1)
x1(t)

x2(t)

0

1

00

0,00

-

01

-

0,01

10

0,01

0,10



3. Карты Карнау:

q(t)=не(x1) (t) не(х2)(t)

q(t)= не(х1)(t) не (q) (t-1)




0

1

00

1

-

01

-

0

11

-

-

10

0

0

Y2





0

1

00

0

-

01

-

1

11

-

-

10

1

0
Y1




0

1

00

0

-

01

-

0

11

-

-

10

0

1


y1(t)= x1(t)q(t-1) y2(t)=x2(t) v x1(t) не(q)(t-1)

y1(t)=не(x2)(t)q(t-1)


6.Кодирование сигналов. Схема автомата. Элемент единичной задержки.

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

Задержка обозначается так: Верхний отросток называется входом, а нижний выходом элемента задержки.

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

Схема их функциональных элементов определяется индуктивно:

1. Совокупность полюсов ( кружков, помеченных символами переменных ) есть схема; все полюсы являются её вершинами.

2. Результат присоединения к вершинам схемы всех входов некоторого элемента ( функционального элемента или элемента задержки ) есть схема; вершинами новой схемы являются все вершины исходной схемы и выход присоединённого элемента, а полюсами – все полюсы исходной схемы.

3. Результат присоединения выхода задержки к некоторому полюсу x1 есть схема; её вершинами являются все вершины исходной схемы, за исключением x1, а полюсами – все полюсы исходной схемы, кроме x1. Операция, соответствующая пункту 3. , называется введением обратной связи.

Cложность схемы – число эл-тов включая л.з. ; Состояния – совокупность состояний всех л.з.; Число л.з. в схеме равно числу двоичных разрядов, необходимых для кодирования всех символов из мн-ва Q. Если схему построить верно, то необх. вып. след. условия:

1. Вход элемента подсоединяется либо полюсу, либо к выходу другого элемента . 2. В кажд. цепочке обр. связи имеет. хотя бы 1 лин. задер.

Кодирование алфавита:

X,Y,Q

*

xi-i-1; yi-i-1

Тогда ур-ие (*) :

yi(t)=F(x1(t),x2(t),…,xs(t),q1(t-1),…,qn(t-1)

qj(t)=G(x1(t)…xs(t),q1(t-1)…qn(t-1)) (1?j?4)

qj(0)=qi0 (1?i?V)

y-V знач. ч. ; x-S знач. ч.; q=u знач. ч.;

7.Задача о дешифрирующем устройстве.

ДЕШИФРИРУЮЩЕЕ УСТРОЙСТВО – это инициальный конечный автомат, который выдает 0 при произвольной последовательности входных символов, и выдает 1 только в том случае когда посл–ность символов образует заданное слово (xi1, xi2,…, xik).

F(j, xi)= G(j,xi)=

Число состояний авт.= числу заданных символов слова k. Каждый поступивший символ заданного слова перебрасывает авт. в очередное состояние.Согласно уравнениям авт. должен перебрасываться в нач. сост., если символ не совпадает с символом слова. Но на практике, чтобы не пропустить не одного слова будем перебрасывать автомат в некоторые промежуточные но не начальные сост.

пример: [xyxy] X={x,y}

?ЇЇЇЇЇЇЇЇЇЇЇЇy(0) ЇЇЇЇЇЇЇЇЇЇЇ| ?ЇЇЇЇ y(1)ЇЇЇЇЇ|

( 1 )----x(0)---?( 2 )-----y(0)--?( 3 )----x(0)---?( 4 )

|_? ?_|?____ x(0)___________________|

y(0) x(0)
8.Представление событий в автоматах. Алгебра регулярных событий.

Событием наз . любая конечная последовательность слов данного алфавита. События представимы в автомате, если с пом. символов события можно придти из начального состояния в конечное.

Алгебра рег. событий:

Предположим, задано 2 события E1 и Е2. Имеют место след. операции: 1. объединение E1 V E2 ; 2. конкатенация E1*E2;

3. Итерация E1=e V E1 V V … V V … =

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

Регулярное событие – событие вида {a1}, {a2}, {a3}

Алгебра рег. событий – это множество регулярных событий простых : объединение, конкатенация, итерация . {R;V;*}
9.Детерминизация источников и синтез автоматов.

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

При вычеркивании источника надо иметь в виду:

___E1___

1) E1U E2 ( ) ( )

ЇЇЇE2ЇЇЇ

2) E1 · E2 ( )-----E1------( )-----E2-----( )
3)Итерация * ( нач.)?--------( закл.)

|_____E1 _____?

Источник наз. ДЕТЕРМЕНИРОВАННЫМ если он удолетворяет след. условиям:Иметься только 1 нач.сост.;В нем нет пустых ребер;Для  вершины a и для  x из X(символ входного слова) имеется ровно 1 дуга выходящая из вершины a и помеченная этим символом.;

Известно что для  источника существует эквивалентный ему детерминированный источник.

МЕТОД СИНТЕЗА ИСТОЧНИКА ПРЕДСТ. СОБЫТИЕ

1)Строим диаграмму соб.2)Составляем табл. не детерминированного источ.;3)Детерменируем его.

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации