← Все тренажёры Формальные языки, регулярные выражения и конечные автоматы

Формальные языки, регулярные выражения и конечные автоматы

Слова и языки, операции, ДКА, НКА и теорема Клини.

22 задания · Конечные автоматы

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

Режим
Режим

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

1

Чем различаются ∅\varnothing и {ε}\{\varepsilon\}?

2

Чему равно Σ0\Sigma^0?

3

Что такое формальный язык над Σ\Sigma?

4

Какой язык задаёт (a∣b)∗b(a\mid b)^*b?

5

Что является условием принятия слова полным ДКА?

6

Как устроена функция переходов ДКА?

7

Когда НКА принимает слово?

8

Что означает ε-переход?

9

Что утверждает теорема Клини?

10

Какую память добавляет автомат с магазинной памятью?

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

11

Сколько слов длины 4 существует над алфавитом из двух символов?

целое число

12

Сколько слов длины не больше 2 существует над алфавитом {a,b}\{a,b\}, включая пустое?

целое число

13

Сколько символов содержит пустое слово?

целое число

14

ДКА чётности единиц стартует в допускающем состоянии E, символ 0 сохраняет состояние, 1 меняет E и O. Принимается ли 1011? Введите 1 для да, 0 для нет.

целое число

15

Сколько слов длины 3 принадлежит языку (a∣b)∗b(a\mid b)^*b?

целое число

16

Пусть L={a,b}L=\{a,b\}, M={a}M=\{a\}. Сколько различных слов в LMLM?

целое число

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

17

Какие тождества языков верны для любого LL?

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

18

Какие слова принадлежат языку (ab)∗(ab)^*?

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

19

Какие утверждения о полном ДКА верны?

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

20

Какие утверждения о НКА верны?

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

21

Какие операции входят в определение классических регулярных выражений?

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

22

Что верно о словах и языках?

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

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

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

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

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

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

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