76. Правила грамматики регламентируют…

1. Какие символы являются терминальными, а какие – нетерминальными.

2. Какие символы являются начальными, а какие – нет.

3. Замену слов, содержащих только терминальные символы, на другие слова.

4. Замену слов, содержащих хотя бы один нетерминальный символ, на другие слова.

5. Замену слов, содержащих хотя бы один терминальный символ, на другие слова.

77. К какому типу грамматик в иерархии Хомского относится грамматика s→aA, a→aA|bB, b→bB|ε ?

1. Грамматика общего вида.

2. Контекстно-зависимая грамматика.

3. Контекстно-свободная грамматика.

4. Автоматная грамматика.

5. Тип грамматики определить нельзя.

78. Автоматная грамматика называется детерминированной, если…

1. Для любого нетерминала A и любого терминала a существует не более одного нетерминала B, для которого имеется правило A→aB.

2. Для любого нетерминала A и любого терминала a существует один и только один нетерминал B, для которого имеется правило A→aB.

3. Существуют нетерминал A и терминал a такие, что для любого нетерминала B не задано правило A→aB.

4. Определен начальный символ грамматики.

5. В грамматике определен ровно один нетерминальный символ.

79. Конечный автомат, как частный случай распознавателя, – это распознаватель, в котором…

1. Указатель на каждом такте смещается вправо или остается на месте, внешняя память отсутствует.

2. Указатель на каждом такте смещается вправо, внешняя память отсутствует.

3. Указатель на каждом такте смещается вправо или остается на месте, внешняя память представляет собой стек.

4. Указатель на каждом такте смещается вправо, внешняя память представляет собой стек.

5. Указатель на каждом такте смещается вправо или влево, внешняя память отсутствует.

80. Пусть {0, 1, 2} – состояния машины Тьюринга (0 – начальное, 2 – заключительное), {L, R, N} – направления смещения указателя (L – влево, R – вправо, N – на месте), {a, b, c} – входные символы. Какая из команд не меняет конфигурацию машины Тьюринга?

1. 0 a → 0 a R

2. 0 a → 2 a N

3. 0 a → 1 a N

4. 0 a → 0 a L

5. 0 a → 0 a N

81. Система уравнений a(t+1) = δ(a(t), z(t)), w(t) = λ(a(t), z(t)), u(t) = μ(a(t)) является функциональной моделью…

1. Автомата Мили.

2. Автомата Мура.

3. C-автомата.

4. Машины Тьюринга.

5. Распознавателя с магазинной памятью.

82. Автомат Мили задается…

1. Таблицей выходов.

2. Таблицей переходов.

3. Таблицей переходов и таблицей выходов.

4. Отмеченной таблицей переходов.

5. Отмеченной таблицей переходов и таблицей выходов.

83. При преобразовании автомата Мили в эквивалентный автомат Мура…

1. Число состояний может увеличиться.

2. Число состояний обязательно увеличится.

3. Число состояний должно остаться прежним.

4. Число состояний обязательно уменьшится.

5. Число состояний может уменьшиться.

84. При минимизации автомата Мура методом последовательных разбиений, на первом шаге алгоритма множество состояний разбивается на подмножества 0-эквивалентных состояний по следующему принципу.

1. Объединяются состояния, для которых столбцы в отмеченной таблице переходов совпадают.

2. Объединяются состояния, для которых совпадают столбцы в отмеченной таблице переходов и которые одинаково отмечены в этой же таблице (совпадают выходные сигналы).

3. Объединяются состояния, которые одинаково отмечены в отмеченной таблице переходов (совпадают выходные сигналы).

4. Состояния группируются произвольным образом.

5. Каждое состояние образует отдельное подмножество.

85. Представленная таблица…

	0	1
0	0	1
1	1	0

1. Задает функцию входов элемента задержки.

2. Задает функцию входов триггера со счетным входом.

3. Задает функцию переходов триггера со счетным входом.

4. Задает функцию переходов триггера с раздельными входами.

5. Задает функцию переходов элемента задержки.

86. Логический элемент – это…

1. Элементарный комбинационный автомат.

2. Элементарный последовательный автомат.

3. С-автомат.

4. Распознаватель.

5. Машина Тьюринга.

87. Сколько выходных каналов понадобится для структурного синтеза автомата Мили, абстрактная модель которого насчитывает 9 выходных сигналов?

1. 3

2. 4

3. 5

4. 8

5. 9

88. Пусть граф автомата насчитывает 10 дуг (петель нет). И пусть состояния автомата закодированы «алгоритмом соседнего кодирования». Оцените качество кодирования k.

1. k = 0.

2. k = 1.

3. k = 10.

4. k = log₂10.

5. k = 10².

89. Если по одной ГСА синтезировать микропрограммный автомат Мили и микропрограммный автомат Мура, то…

1. В автомате Мили будет ровно столько же состояний, сколько и в автомате Мура.

2. Число состояний в автомате Мили будет не больше, чем в автомате Мура.

3. Число состояний в автомате Мили будет строго больше, чем в автомате Мура.

4. Графы автоматов совпадут.

5. Логические схемы автоматов совпадут.

90. Число столбцов в прямом структурном списке микропрограммного автомата Мили равно…

1. 3

2. 4

3. 5

4. 6

5. 7

11