Теория экспериментов с конечными автоматами

Упражнение 1:

Номер 1

Обобщенными автоматами без потери информации (ОБПИ-автоматами) называются

Ответ:

(1) автоматы, для которых задача распознавания проекции слова math

может быть решена независимо от входного слова и действительного начального состояния из множества math

(2) автоматы, для которых задача распознавания проекции слова math

может быть решена независимо от выходного слова и действительного начального состояния из множества math

(3) автоматы, для которых задача распознавания проекции слова math

может быть решена независимо от входного слова и действительного конечного состояния из множества math

Номер 2

Укажите верное утверждение:

Ответ:

(1) две вершины графа могут связываться несколькими дугами с разными пометками

(2) две вершины графа не могут связываться несколькими дугами с разными пометками

(3) две вершины графа могут связываться одной дугой

Номер 3

ОБПИ-автоматы в качестве частного случая включают в себя

Ответ:

(1) БПИ-автоматы

(2) СБПИ-автоматы

(3) БПИК-автоматы

Упражнение 2:

Номер 1

Если выполняется , то пара состояний  и  называется

Ответ:

(1) состояниями с частичной потерей информации (СПИ-состояниями)

(2) состояниями без потери информации

(3) состояниями с потерей информации

Номер 2

Укажите верное утверждение:

Ответ:

(1) для того чтобы автомат math

был ОБПИ-автоматом, необходимо и достаточно, чтобы он не имел СПИ-состояний

(2) для того чтобы автомат math

был ОБПИ-автоматом, необходимо и достаточно, чтобы он имел ограниченное множество СПИ-состояний

(3) для того чтобы автомат math

был ОБПИ-автоматом, необходимо и достаточно, чтобы он имел одно СПИ-состояние

Номер 3

Укажите верное утверждение:

Ответ:

(1) теорема об условии существовании ОБПИ-автомата не позволяет обосновать метод восстановления искомой проекции неизвестного входного слова.

(2) теорема об условии существовании ОБПИ-автомата позволяет обосновать метод восстановления искомой проекции неизвестного входного слова

(3) теорема об условии существовании ОБПИ-автомата при любых условиях не дает ответа на вопрос, является ли конкретный автомат ОБПИ-автоматом

Упражнение 3:

Номер 1

Если из ориентированного конечного графа   удалить все вершины вида  вместе с инцидентными им дугами, если последние, в свою очередь, инцидентны только вершинам такого же вида, а также изолированные вершины, то полученный в результате такого удаления ориентированный конечный граф называется

Ответ:

(1) удаленным графом автомата math

(2) проверочным графом автомата math

(3) аналитическим графом автомата math

Номер 2

Укажите верное утверждение:

Ответ:

(1) автомат является ОБПИ-автоматом тогда и только тогда, когда все пути в проверочном графе math

, ведущие из вершин вида math

, не содержат выделенных дуг

(2) автомат является ОБПИ-автоматом тогда и только тогда, когда все пути в проверочном графе math

, ведущие в вершины вида math

, не содержат выделенных дуг

(3) автомат является ОБПИ-автоматом тогда и только тогда, когда все пути в проверочном графе math

, ведущие в вершины вида math

, содержат хотя бы одну выделенную дугу

Номер 3

Автомат называется оптимальным, если

Ответ:

(1) подмножество входных каналов - минимальное, а подмножество выходных каналов - максимальное по мощности

(2) подмножество входных и выходных каналов - минимальное по мощности

(3) подмножество входных каналов - максимальное, а подмножество выходных каналов - минимальное по мощности

Упражнение 4:

Номер 1

ОБПИК-автоматы в качестве частного случая включают в себя

Ответ:

(1) БПИК-автоматы

(2) СБПИК-автоматы

(3) БПИ-автоматы

Номер 2

Укажите верное утверждение:

Ответ:

(1) автомат math

является ОБПИК-автоматом тогда и только тогда, когда в его проверочном графе все контуры не содержат выделенных дуг

(2) автомат math

является ОБПИК-автоматом тогда и только тогда, когда в его проверочном графе все пути, ведущие в контуры, не содержат выделенных дуг

(3) автомат math

является ОБПИК-автоматом тогда и только тогда, когда в его проверочном графе все контуры и все пути, ведущие в эти контуры, не содержат выделенных дуг

Номер 3

Если в проверочном графе ОБПИК-автомата  длина максимального пути, начальная дуга которого является выделенной, равна , то порядок ОБПИК-автомата  равен

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

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

Ответ:

(1) первого символа неизвестного входного слова

(2) последнего символа неизвестного входного слова

(3)

-го символа неизвестного входного слова

Номер 2

Для того, чтобы однозначно определить число  оно должно быть

Ответ:

(1) максимальным из всех возможных для заданного автомата math

чисел такого рода

(2) минимальным из всех возможных для заданного автомата math

чисел такого рода

(3) суммой из всех возможных для заданного автомата math

чисел такого рода

Номер 3

Пусть автомат  не является ОБПИК-автоматом,, , тогда

Ответ:

(1) будет равен 2

(2) будет равен 0

(3) не может быть определен

Упражнение 6:

Номер 1

Укажите верное утверждение:

Ответ:

(1) задачу контроля сети автоматов можно свести к задаче контроля одного автомата

(2) задачу контроля сети автоматов нельзя свести к задаче контроля одного автомата

(3) задачу контроля сети автоматов можно свести к задаче контроля одного автомата, только если сеть состоит не более чем из 3 автоматов

Номер 2

Для решения задачи контроля сети автоматов, исходный произвольный автомат следует преобразовывать в БПИ-автомат

Ответ:

(1) БПИ-автомат

(2) БПИК-автомат

(3) ББИ-автомат

Номер 3

Укажите верное утверждение

Ответ:

(1) если событие math

в алфавите math

, регулярное выражение которого есть math

, представимо в автомате math

, то проверочные графы math

и

, где

получено из math

путем замены каждого вхождения итерации события math

на

, совпадают

(2) если событие math

в алфавите math

, регулярное выражение которого есть math

, представимо в автомате math

, то проверочные графы math

и

, где

получено из math

путем замены каждого вхождения итерации события math

на

, не совпадают

(3) если событие math

в алфавите math

, регулярное выражение которого есть math

, представимо в автомате math

, то проверочные графы math

и

, где

получено из math

путем замены каждого вхождения итерации события math

на

,только иногда совпадают

Упражнение 7:

Номер 1

        В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. . На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если состояние автомата равно 1, то конечное состояние будет равно

Ответ:

(1) 1

(2) 2

(3) 3

Номер 2

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. . На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если состояние автомата равно 2, то конечное состояние будет равно

Ответ:

(1) 1

(2) 2

(3) 3

Номер 3

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу. . На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если состояние автомата равно 3, то конечное состояние будет равно

Ответ:

(1) 1

(2) 2

(3) 3

Упражнение 8:

Номер 1

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу.  На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если , то проекцией по 1-му входному каналу неизвестного входного слова является

Ответ:

(1) 1,0,1

(2) 1,1,1

(3) 1,0,0

Номер 2

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу.  На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если , то проекцией по 1-му входному каналу неизвестного входного слова является

Ответ:

(1) 1,0,1

(2) 1,0,0

(3) 1,0,0

Номер 3

В приведенном рисунке для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу.  На автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдается реакция 0,1,1., Если , то проекцией по 1-му входному каналу неизвестного входного слова является

Ответ:

(1) 1,1,1

(2) 1,0,0

(3) 1,0,1

Теория экспериментов с конечными автоматами - тест 5