2001-gre-vs-practice.pdf/Q50

Ссылки сюда (1) →

Задача зарезервирована: илья52 19:05, 22 декабря 2024 (UTC)

Пусть . Пусть - набор строк в , таких, что , тогда и только тогда, когда количество нулей в делится на , а число единиц в нечетно. Чему равно минимальное число состояний в детерминированном конечном автомате (DFA), который распознает язык ?

Ответы

• Правильный ответ:
• 2^k

Объяснение

Исходники — вопрос 50 на 38 странице книги «2001-gre-vs-practice.pdf»

Количество нулей должно делиться на . Для этого нам потребуется состояний, чтобы отслеживать остаток от деления количества нулей на : , где состояние соответствует тому, что мы увидели нулей по модулю .

Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется состояния:

Состояния в автомате, распознающим язык будут представлены парами . Количество всевозможных пар равно . Решено: илья52 10:37, 7 января 2025 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.