Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

161

Рисунок 9.19 – Получение кодированной матрицы переходов

Рисунок 9.20 – Пример формы получения таблицы возбужде-

ния

162

На четвертом шаге структурного синтеза формируются

и выводятся на экран аналитические выражения для функций

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

сунке 9.21.

Рисунок 9.21 – Пример формы получения функций выходов и

возбуждения

На пятом этапе функции выходов и возбуждения ми-

нимизируются путем задания склеек. Пример формы для это-

го этапа

структурного синтеза представлен на рисунке 9.22.

Нажатие на кнопку «Добавить склейку» на этой

форме используется для добавления одной склейки в теку-

щую карту Карно. Пример формы приведен на рисунке 9.23.

Для того чтобы внести ячейку таблицы в склейку необходи-

мо нажать на неё, при этом она выделится красным цветом.

Чтобы убрать ячейку из

склейки необходимо нажать на неё

повторно, при этом она снова станет белой.

163

Рисунок 9.22 – Пример формы для минимизации функций

Рисунок 9.23 – Пример формы добавления склейки

164

Если склейка неверная, то пользователь увидит соот-

ветствующее сообщение (рисунок 9.24).

Рисунок 9.24 – Сообщение при неверном задании склейки

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

ния и выходов открывается новая форма. Пример такой фор-

мы представлен на рисунке 9.24.

Рисунок 9.24 – Пример формы с результатом структурного

синтеза

165

10 МАТЕРИАЛ ДЛЯ САМОКОНТРОЛЯ

Для проверки усвоения материала, изложенного в

учебном пособии, предлагается ответить на следующие во-

просы:

1. Неформальное определение автомата.

2. Что такое конечный автомат?

3. Какие типы алфавитов существуют для абстрактных

автоматов?

4. Чем отличаются автоматы синхронного и аснхронно-

го действия?

5. Формальное определение конечного автомата-

распознавателя.

6. Какой из этих автоматов является детерминирован-

ным:

7. Может ли автомат быть неинициальным?

8. В чем заключается отличие полностью определенного

автомата от частичного?

9. Что такое функция выходов?

10. Сколько заключительных состояний может иметь ко-

нечный автомат-распознаватель?

11. Что такое регулярный язык?

12. Как задается конечный автомат-распознаватель?

13. Как удалить цикл из начального состояния автомата?

14. Как удалить цикл из заключительного состояния ав-

томата?

166

15. Приведите пример синтеза автомата-распознавателя,

когда требуется удаление цикла из начального со-

стояния.

16. Приведите пример синтеза автомата-распознавателя,

когда требуется удаление цикла из заключительных

состояний.

17. Зачем при построении автомата, распознающего до-

полнение регулярного языка, нужна детерминизация?

18. Что такое эквивалентные состояиия?

19. Что такое минимальный автомат?

20. Как

строится минимальный автомат, эквивалентный

заданному?

21. Какое максимальное число разбиений при минимиза-

ции автомата?

22. Постройте леволинейную и праволинейную грамма-

тики, порождающие язык, распознаваемый заданным

автоматом:

23. Автоматом какого типа распознается КС-язык?

24. Как устроен магазин МП-автомата?

25. Зачем в магазин МП-автомата при нисходящем раз-

боре помещается

зеркальная правая часть правила?

26. Что такое функция переходов машины Тьюринга?

27. Что такое конфигурация?

28. В чем особенность стандартных конфигураций?

29. Как задается машина Тьюринга?

30. Как работает машина Тьюринга при вычислении

функции f(x

,…,x

167

31. Может ли машина Тьюринга зациклиться при выпол-

нении вычислений?

32. Чем отличаются законы функционирования автома-

тов Мили и автоматов Мура?

33. Как строится совмещенная таблица для автомата Ми-

ли?

34. Как графически задается автомат Мили?

35. Как графически задается автомат Мура?

36. Что такое реакция автомата?

37. Как изменяется количество

состояний при переходе

от автомата Мили к автомату Мура?

38. Как изменяется количество состояний при переходе

от автомата Мили к автомату Мура?

39. Как строятся таблицы разбиения при минимизации

преобразователя?

40. Чем отличаются установочная и контролирующая по-

следовательность?

41. Как строится дерево для определения установочной

последовательности?

42. Понятие события в

модели сетей Петри.

43. Как учитывается время в сетях Петри?

44. Что такое емкость условия?

45. Как строится графическое представление сетей Пет-

ри?

46. Что такое разметка позиции?

47. Приведите формальное определение сетей Петри.

48. Каким образом происходит изменение маркировки

сети?

49. Как моделируются непримитивные события?

50. Что такое приоритетные сети

51. Что такое структурный синтез автомата?

52. Какие существуют типы элементарных автоматов?

53. Как определить, что автомат имеет полную систему

переходов?

54. Что такое канонические уравнения?

55. Что такое триггер?

168

56. Зачем используется синхросигнал?

57. При каком условии T-триггер изменяет свое состоя-

ние?

58. Запишите закон изменения состояний D-триггера.

59. Что такое таблица функций возбуждения?

60. Как строится таблица функций возбуждения?

61. Какие сигналы запрещены для R-S-триггеров?

62. Что такое автомат с избыточной системой переходов?

63. В чем заключается отличие J-K-триггера

от R-S-

триггера.

64. Какова роль элементов памяти и комбинационной

схемы в обобщенной структурной схеме автомата?

65. Что такое функция возбуждения?

66. Поясните назначение функции возбуждения.

67. Как определить число элементов памяти для синтеза

структурного автомата?

68. Как определить количество входных и выходных ка-

налов для синтеза структурного автомата?

69. Что

такое функция обратной связи?

70. Как строятся функции возбуждения?

71. Как строятся функции выходов?

72. Что такое код Грея и как он формируется?

73. Как зеркальный код применяется для минимизации

функций?

74. Что такое импликанта?

75. Сколько клеток может быть внутри контура в карте

Карно?

76. Сколько раз единица (ноль) может

входить в контур в

карте Карно?

77. Как строятся элементарные конъюнкты (дизъюнкты)

для контура?

78. Как строится таблица функции возбуждения для Т-

триггера?

79. Что такое асинхронный автомат?

80. Какими свойствами обладают входные сигналы в

асинхронных автоматах?

169

81. Что такое состязания в автоматах?

82. Зачем устраняют гонки?

83. Какие способы устранения гонок существуют?

84. Как выполняется соседнее кодирование?

85. Что такое микрооперация?

86. Приведите примеры микроопераций.

87. Что такое микропрограмма?

88. Какие функции реализует операционный автомат?

89. Поясните назначение управляющего автомата.

90. Что такое ГСА?

91. Чем отличаются

содержательная и кодированная

ГСА?

92. Что такое операционный элемент?

93. Перечислите типы операционных элементов.

94. Что такое микропрограммный автомат?

95. Как строится отмеченная ГСА для автомата Мили?

96. Как строится отмеченная ГСА для автомата Мура?

170

Список использованных источников:

Карпов Ю. Г. Теория автоматов [Текст]: учебник для

вузов по направлению подготовки бакалавров "Инфор-

матика и вычислительная техника" и по специальности

"Вычислительные машины, комплексы, системы и се-

ти" направления подготовки дипломированных специа-

листов "Информатика и вычислительная техника" /Ю.

Г. Карпов.-СПб.: Питер, 2002. - 206 с.: ил..-( Учебник

для вузов ).

2. Белоусов, А.И

. Дискретная математика [Текст]:

учебник для втузов /А. И. Белоусов, С. Б. Ткачев ; под

ред. В. С. Зарубина, А. П. Крищенко.-М.: Изд-во МГТУ

, 2004.-744 с.: ил.

3. Нарышкин, А.К. Цифровые устройства и микропро-

цессоры: учебное пособие для вузов радиотехнических

специальностей [Текст] /А. К. Нарышкин .-М.: Акаде-

мия, 2006.-317 с.

4. Хопрофт

, Дж. Введение в теорию автоматов, языков и

вычислений [Текст] / Джон Хопрофт, Раджив Мотвани,

Джерри Ульман. – Изд-во Вильямс, 2007. – 528 с.

5. Лупал, А.М. Теория автоматов [Электронный ресурс]:

учебное пособие/ А.М. Лупал. – СПб: ГУАП, 2000. –

119 с. Режим доступа

http://window.edu.ru/window_catalog/files/r44618/2000-

0049-0-01.pdf и

http://window.edu.ru/window_catalog/files/r44618/2000-

0049-0-02.pdf