Устройство для моделирования конечных автоматов

383043

ОПИСАНИЕ

ИЗОЫЕтЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Со@ивлистииеских

Республик

Зависимое от авт. свидетельства №

Заявлено liO.Õ1.1969 (№ 13753 20/18-24 с присоединением заявки №

Приоритет

Опубликовано 23.Н.1973. Бюллетень ¹ 23

Дата опубликования описания 26.IX.1973

М. Кл. G 06f 7 38 государственный комитет

Совета Министров СССР по делам изобретений и открытий

УДК 681.332:371.69 (088.8) Автор изобретения

В. В. Серебринский

Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

КО Н ЕЧ Н Ъ| Х А В ТОМАТО В

Изобретение относится к области вычислительной техяики.

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

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

Предлагаемое устройство с целью его

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

На чертеже приведена блок-схема устройства. Устройство содержит блок памяти 1, 15 блок управления 2, дешифратор служебных символов 8, элементы «И» 4 и 5. триггер б, регистр аргументов 7, регистр функций 8, дешифратор аргументов 9, дешифратор функц»й возбуждения 10, дешифратор функций

20 выхода 11, элемент «И» 12, регистр функций выхода 18, блок вычисления булевых функций 14 с выходами 15 и 16, элемент «И» 17, регистр . состояний 18, сумматор по модулю два 19, коммутатор 20, регистр набора aipry25 ментов 21.

Устройство работает следующим образом.

Для определения значений булевых функций по их алгебраическим выражениям последние представляются в дизъюнктивных з0 формах, по которым составляется програм383043

3 ма. Для этого каждая булевая функция записывается в виде одного слова. Например, функция у;=х х2+х х2 будет запиеана следующим образом: ауфх,х, Ax,х,Ла, где а — служебный символ, за которым следует символ функции у;;

Л вЂ” служебный символ раздела между дизъюнктивныии членами, служащий также вместо знака равенства; о — служебный символ конца программы, который ставится в конце последнего выражения функции; х;, х — аргументы.

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

В полученном слове каждой букве присваива ется определенное двоичное число — двоичный код.

Полученный ряд кодов записывается в блок памяти 1. Кроме кода каждому аргументу присваивается еще определенное значение «О» или «1», которые вместе с кодом аргумента вносятся в каждую ячейку блока памяти 1. Это значение аргумента вносится в специальный разряд ячейки блока памяти.

Если аргумент входит в формулу без знака отрицания, то в специальный разряд заносится «1», если со знаком отрицания, то «О».

Служебным символам « " », «а» и «а», а также символам функций присваивается «1» в специальном разряде. Для получения значений булевых функций производится вывод из блока памяти всех символов (т. е. их кодов и значений в специальном разряде) в порядке их записи.

Первый выведенный из блока памяти символ «а» дешифрируется с помощью дешифратора служебных символов 3 и устанавливает триггер б в состояние, при котором на элемент «И» 4 подается разрешающий потенциал. Следующий символ у, проходит через элемент «И» 4, попадает на регистр функций и дешифрируется дешифратором функций возбуждения 10 или дешифратором функций выхода 11, в за висимости от того, является ли этот символ функцией возбуждения или выходов. В результате этого на одном из выходов дешифратора функций возбуждения 10 или дешифратора функций выхода 11 появляется разрешающий лотенциал, подаваемый на элементы «И» 12 и 17.

Следующий за «у,» символ «Л», дешифри; руясь с помощью дешифратора служебных символов 8, перебросит триггер б. При этом будет подан разрешающий потенциал на элемент «И» 5. Код аргумента, следующего за

« », будет подан на регистр аргументов 7 и дешифрирован с помощью дешифра тора аргументов 9. В результате на одном из выходов дешифратора аргументов 9 появляется разрешающий потенциал, который, воздейст5

40 вуя на коммутатор 20, произведет выбор аргумента на регистре набора аргументов 21 или регистра состояний 18. Это значение аргумента подается на один из входов сумматора по модулю два 19, на второй вход которого подается значение а ргумента из специального разряда блока памяти. Если окажется, что значение аргумента в специальном разряде блока памяти 1 и его значение на выходе коммутатора 20 будут одинаковы, то будет выдана «1» на выходе а сумматора по модулю два 19. Если же значения аргументов на входе сумматора по модулю два 19 не совпадают, то «1» появится па выходе b.

После этого поступает следующий аргумент на регистр аргументов 7 и с ним производится такая же операция.

Поступление сигнала на любой из входов а, b, а, и Л блока вычисления булевых функций 14 означает появление на его обобщенном входе любой из перечисленных букв а, b, а или . Эти буквы составляют входной алфавит этого блока.

Сигнал на выходе 15 блока вычисления булевых функций 14 появляется в том случае, если входное слово будет содержать такую его часть, в которой между буквами Л будут только буквы а.

Сигнал на выходе lб блока вычисления булевых функций 14 появляется в том случае, если входное слово будет содержать между всеми парами букв Ь хотя бы одну букву b. При этом имеется в виду, что входное слово образуется в результате обработки алгебраического выражения одной из булевых функций.

Если условия появления сигналов на выходах 15 и lб выразить на языке регулярных выражений и обозначить как события S> и S, то последние будут иметь следующие выражения:

S, = аЛ {Ь {a+ b) Л + и {а) 6,а +

+b} Л}а}а)6 а+о+А! а, S, = аЬ (b {a+b> А+а {a}b!a+b; Л) {b, a+b) Л+

+ а {а} b {а+ b, Л) z.

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

Сигнал на выходе 15 появляется в том случае, когда булевая функция равна «1», а сигнал на выходе lб, если она равна «О».

Любое из значен" é функций выходов будет зафиксировано на регистре функций выхода 18 с помощью элемента «И» 12 и дешифратора функций выхода 11 и сохранено до последующего цикла работы блока памяти 1.

При обработке функций возбуждения будет произведена установка каждого разряда регистра состояний 18 в соответствии со значением функции возбуждения, полученной

383043

15

З0

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

B конце цикла работы блока памяти 1 с в:.хсда дешифратора служебных символов 8 г,ыдается сигнал в результате дешифрировани:> символа чв». Этот сигнал может быть использован для формирования следующего набора аргументов на регистре набора аргументов 21.

Таким образом, с каждым циклом ра|боты б.-.ока памяти 1 на регистрах состояний 18 и регистре функций выхода 18 будут появляться новые кодируемые состояния и выходы, т. е. последовательности состояний и выходов, которые можно рассматривать как реакции на входную последовательность, подаваемую на регистр набора аргументов 21.

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

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

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

Предмет изобретения

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

383043

Редактор Е. Гончар

Заказ 2298/8 Изд. Ко 613 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР .11осква, )К-35, Рзушская паб., д. 4, 5

Типография, II).. Сапунова, 2

Составитель Г. Сорокин

Техред Е. Борисова

Корректоры: А. Дзесова и О. Тюрина