← Все тренажёры Преобразования и минимизация конечных автоматов

Преобразования и минимизация конечных автоматов

ε-замыкание, построение подмножеств, Томпсон и минимальный ДКА.

15 заданий · Конечные автоматы

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Что содержит ε-замыкание множества SS?

2

Чему соответствует состояние ДКА при построении подмножеств?

3

Какое подмножество является допускающим при детерминизации?

4

Как выбирают стартовое множество при детерминизации ε-НКА с одним стартом q0q_0?

5

Что означает достижимое пустое подмножество в построенном полном ДКА?

6

Что делает конструкция Томпсона?

7

Какие состояния ДКА эквивалентны?

Блок 2. Краткий ответ

8

Какова общая верхняя граница числа состояний при детерминизации НКА с 3 состояниями?

целое число

9

Есть ε-дуги p→qp\to q, q→rq\to r, других ε-дуг нет. Сколько состояний содержит E({p})E(\{p\})?

целое число

10

У НКА δ(p,a)={p,q}\delta(p,a)=\{p,q\}, δ(q,a)=∅\delta(q,a)=\varnothing, ε-дуг нет. Сколько состояний в множестве D({p,q},a)D(\{p,q\},a)?

целое число

11

НКА: старт p; δ(p,a)={p,q}\delta(p,a)=\{p,q\}, δ(p,b)={p}\delta(p,b)=\{p\}; из q переходов нет. Сколько достижимых подмножеств возникает при детерминизации?

целое число

12

Сколько состояний в минимальном полном ДКА для языка всех двоичных слов с чётным числом единиц?

целое число

Блок 3. Несколько верных вариантов

13

Какие свойства ε-замыкания верны?

Отметьте все верные варианты

14

Что нужно учитывать при удалении ε-переходов?

Отметьте все верные варианты

15

Какие утверждения о детерминизации верны?

Отметьте все верные варианты

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (15)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.